[Java] 백준(실버-3) 2579번 - 계단 오르기

문제 풀이

---

이 문제는 동적 계획법(DP)를 이용해 풀 수 있는 문제이다.

아이디어 도출

이 문제에서는 Top-Down 방식과 Bottom-Up 방식 중 Top-Down 방식으로 풀기 위해 재귀를 이용했다.

먼저 문제의 제약사항은 다음과 같다.

• 계단은 한 번에 한 계단, 두 계단씩만 오를 수 있다
• 연속된 3개의 계단을 밟으면 안된다

위 조건을 토대로 N번째 계단을 밟는 경우를 따져보면 N-3을 밟고 N-1번 계단을 밟고 오는 경우와 N-2번을 밟고 오는 경우 2가지가 존재한다. 위 2가지 말고는 연속으로 3개의 계단을 밟는 것은 불가능하기 때문에 이외의 경우는 존재하지 않는다.

또한, 계단의 점수가 입력된 배열을 arr, DP 테이블을 D라고 한다면, 마지막 칸은 무조건 밟아야 하므로 N번째 계단을 밟았을 때의 점화식을 다음과 같이 도출할 수 있다.

3번째 전의 칸을 밟고 1번째 전의 칸을 밝고 오는 경우와 2번째 전의 칸을 밝고 오는 경우 중 더 큰 점수 값 + N번째 칸의 점수 값
D[N] = Math.max(recursion(N-3)+arr[N-1], recursion(N-2)) + arr[N]

유의할 점은 1,2,3번째 계단의 경우 점화식을 대입할 때 3번째 전의 칸이 존재하지 않는다. 이러한 예외를 방지하기 위해 N이 2 이상일 경우 DP 테이블의 0,1,2 번째 값을 갱신해주어야 한다.

문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

import java.io.*;

class Main {    

    // DP 테이블 선언
    static int[] D;
    
    // 계단의 점수를 담을 배열
    static int[] arr;

    public static void main(String[] args) throws IOException {
        
        // 최대 점수를 내려면 최대한 계단을 많이 밟아야 한다.
        // 고로, 1 계단씩 2번 이동한 후 2 계단씩 1번 이동을 반복해야 한다.

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int N = Integer.parseInt(br.readLine());

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

        // DP 테이블 초기화
        for(int i=0; i<=N; i++) {
            D[i] = -1;
        }

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

        // 0번째와 1번째 계단의 점수를 미리 갱신한다.
        D[0] = arr[0];
        D[1] = arr[1];

        /**
         * N이 1일 수도 있기에 그에 대한 예외 처리를 해준다.
         * N-3이 존재하지 않는 경우를 대비
         */
        if(N >= 2) {
            D[2] = arr[1] + arr[2];
        }

        int result = recursion(N);

        bw.write(result+"\n");

        bw.close();
        br.close();
    }

    /**
     * N번째 계단을 밟아가는 경우의 수 중에서 최대점수를 가지는 경우를 구한다.
     * N-3번째 계단을 밟고 N-1번째 계단을 밝고 오는 경우와 N-2번을 밝고 오는 경우 2가지 경우에 대해서 재귀호출한다.
     * N-1번째 계단을 밝는 경우를 재귀 호출하지 않는 이유는 밟은 계단인지 여부가 연속되지 않도록 하기 위함이다.
     * N-2와 N-3에 대해서만 재귀호출해야한다.
     * 그래서, N번째 칸의 최대 점수는 두칸 전의 메모이제이션 값과 셋째 칸 전의 메모이제이션 값 + 첫째 칸 전의 값 중 더 큰 값이 된다.
     */
    static int recursion(int N) {
        if(D[N] == -1) {
            D[N] = Math.max(recursion(N-2), recursion(N-3) + arr[N-1]) + arr[N];
        }
        return D[N];
    }

}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.