[DP/자바] 코드트리 IL.계단 오르기

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 해석

1. n층 높이의 계단을 오르는 경우의 수를 구하는 문제이다.

-> 여기까지만 보면 아직은 어떤 알고리즘을 쓸지 확신하기 어렵다.

2. 2개 또는 3개 계단 단위로만 오를 수 있다고 한다. 

-> 일정 패턴으로만 진행되는 것을 알 수 있다. 이렇게 정형화된 패턴을 배치하는 경우의 수를 구하는 문제는 다이나믹 프로그래밍의 가장 대표적인 유형이다.

 

문제에서 요구하는 답은 n개의 계단을 오르는 경우의 수 이므로 f(n) = n번째 계단을 오르는 경우의 수 일 것이다.

n번째 계단은 n-2번째 계단 또는 n-3번째 계단에서 오르는 경우 1개씩 있는 것이므로 f(n) = f(n-2) + f(n-3)이라는 점화식을 세울 수 있다.

 

점화식을 다 세웠으면 DP 구현 방식인 (1) 메모이제이션 (2) 타뷸레이션 중에서 하나를 고르면 된다. 일단 이번 문제는 매우 간단해서 둘 다 해봤는데, 대부분의 DP 문제는 타뷸레이션으로 풀면 된다. (메모이제이션이 구현 난이도가 조금 더 있는 편이고, 메모이제이션으로만 풀 수 있는 문제가 딱히 출제되지 않기 때문이다. 그러니 그냥 DP는 구현 방법에 메모이제이션도 있고, 메모이제이션의 컨셉 정도가 무엇인지 정도만 이해하고 넘어가자. )

 

주의할 점은, 10007을 나눈 값으로 출력하라는 조건이 있는데, 이는 DP를 진행하다 보면 특정 값부터 int의 max 범위(2^31 -1)를 넘어가기 때문이다. 따라서 MOD 연산을 적절하게 설정해줘야 하는데, 타뷸레이션 값을 저장하는 dp 배열에 값을 저장할때마다 MOD 연산을 해 주는 것이 가장 적절하다.

for (int i = 4; i <= n; i++) {
    dp[i] = dp[i - 2] + dp[i - 3] % 10007; // 적절
}
System.out.println(dp[n]);

출력할 결과들이 dp 배열에 담겨야 하는 것이니 어찌보면 논리상 당연한 말이다. 만약 출력을 할 때에 MOD 연산을 해주게 되면 이미 int 범위를 넘어선 값이 dp배열에 저장되어 있고, 그 값에 대하여 mod 연산을 하게 되는 경우가 생기니 일정 값 이상의 n이 주어지면 정답을 틀리게 된다.

for (int i = 4; i <= n; i++) {
    dp[i] = dp[i - 2] + dp[i - 3];
}
System.out.println(dp[n] % 10007); // 부적절

여기서 왜 하필 10007인지 궁금할 수 있는데, 그냥 적당한 소수를 하나 지정해서 MOD 연산하는 소위 국룰 같은 개념이라고 이해하고 있으면 된다.

 

 

문제 풀이

public class 계단오르기_타뷸레이션 {

    public static void main(String[] args) throws IOException {
        int[] dp = new int[1002];
        dp[0] = 0;
        dp[1] = 0;
        dp[2] = 1;
        dp[3] = 1;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        for (int i = 4; i <= n; i++) {
            dp[i] = dp[i - 2] + dp[i - 3] % 10007;
        }
        System.out.println(dp[n]);

    }
}

public class 계단오르기_메모이제이션 {
    private static int n;
    private static int[] dp;
    public static final int MAX_N = 1001;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        dp = new int[MAX_N];
        for (int i = 0; i < MAX_N; i++) {
            dp[i] = -1;
        }
        int ans = memoization(n);
        if (ans == -1) {
            System.out.println(0);
        } else {
            System.out.println(ans);
        }
    }

    private static int memoization(int i) {
        if (dp[i] != -1) {
            return dp[i];
        }
        if (i == 1) {
            return 0;
        } else if (i == 2 || i == 3) {
            return 1;
        }
        dp[i] = (memoization(i - 2) + memoization(i - 3)) % 10007;
        return dp[i];

    }
}