[백준][JAVA] 2579 계단 오르기

📌문제 설명

백준2579번: 계단 오르기

 

시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 

규칙

• 계단은 한번에 한계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
• 연속된 세 개의 계단을 모두 밟아서는 안된다. 단, 시작점은 계단에 포함되지 않는다.
• 마지막 도착 계단은 반드시 밟아야 한다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성해라.

 

입력

첫째 줄에 계단의 개수가 주어진다. 둘째 줄부터 한 줄에 하나씩 제일 아레에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. (자연수)계단의 개수 <= 300,

(자연수)계단에 쓰여 있는 점수 <= 10,000

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력하자.

 

💡생각

알고리즘 분류를 다이나믹 프로그래밍으로 해서 선택한 문제라서 다이나믹 프로그래밍으로 접근해야겠다고 생각을 하고 문제 풀이를 시작했다. 처음에는 규칙을 찾을려고 노력했지만 이 문제는 아예 감이 안와서 다른분이 하신 걸 참고해서 문제를 풀이했다.

 

[백준]2579번 계단 오르기(java)

[백준]2579번 계단 오르기(java)

 

🔥풀이

올라갈 때 경우의 수는 두가지입니다.

• 한칸 올라가기!
• 두칸 올라가기!

만약 한칸을 올라갔을 때 경우의 수는 한가지입니다.

• 두칸 올라가기!
• 한칸 올라가기 -> 연속된 세개의 계단을 밟을 수 없기 때문에 한칸 올라가기를 두번 동시에 할 수 없다.

만약 두칸을 올라갔을 때 경우의 수는 두가지입니다.

• 한칸 올라가기!
• 두칸 올라가기!

계단이 한개일때는 한칸밖에  못올라갑니다.

계단이 두개일때는 (한칸오르기 + 한칸오르기 > 두칸오르기) 식이 성립됩니다.

계단이 세개인 경우 

• 두칸오르기 + 한칸오르기
• 한칸오르기 + 두칸오르기

계단이 네개인 경우

• 두칸오르기 + 두칸오르기
• 한칸오르기 + 두칸오르기+한칸오르기
• 두칸오르기 + 한칸오르기+한칸오르기 ->연속된 세개의 계단을 밟을 수 없기 때문에 연속으로 한칸오르기가 나오면 안된다!

그리고 마지막계단은 무조건 밟아야 한다는 조건이 있기 때문에 마지막 동작을 수행했을 때 마지막 계단을 밟아져야 한다!!

계단이 4개일때

계단이 네개 이상이라도 상관없다. 우리가 3이상의 계단의 위치에서 생각하면 되는 점수는

• 두칸오르고 두칸오를때 점수
• 한칸오르고 두칸오르고 한칸오를때 점수 두가지를 비교해주면 된다.

그래서 DP[i-3] + arr[i-1] VS DP[i-2] 두가지를 비교해주면 된다.

코드로 작성하면.

import java.io.*;


public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int[] arr = new int[N+1];
        int[] DP = new int[N+1];

        for(int i = 1;i<=N;i++)
        {
            arr[i] = Integer.parseInt(br.readLine());
        }
        DP[1] = arr[1];

        if(N >= 2)
        {
            DP[2] = arr[1] + arr[2];
        }
        for(int i = 3;i<=N;i++)
        {
            DP[i] = Math.max(DP[i-2], DP[i-3] + arr[i - 1]) + arr[i];
        }
        System.out.println(DP[N]);
    }
}

 

이렇게 코드를 작성할 수 있다.