DP) 백준 10844 (Java)

https://www.acmicpc.net/problem/10844

10844번: 쉬운 계단 수

1. 문제 접근

• 맨 왼쪽부터 값을 주었을 때 그 다음에 오는 값은 이전 값에 영향을 받는다. 예를 들어, 계단 수가 2로 시작했다면 그 다음에 올 수 있는 값은 3 또는 1이다.
• 이를 거꾸로 해석하면, 왼쪽에 오는 값도 오른쪽에 있는 값에 따라 달라지며 영향을 받는다는 뜻이다. 즉, N자리 계단수는 N - 1자리의 계단수의 맨 앞에 알맞는 숫자를 붙이기만 하면 되는 것이다. 즉 현재 값과 이전 값들의 관계를 표현할 수 있으며, 점화식으로 나타낼 수 있을 것이다. -> 다이나믹 프로그래밍 적용 문제

2. Top Down 방식 - 메모이제이션

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class No10844 {

    static final long MOD = 1_000_000_000L;
    static Long[][] dp;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        dp = new Long[N + 1][10];

        // NullPoitner 막기 위해서는 0인 경우도 초기화 해야 함 -> 계단수의 마지막이 0으로 끝나는 경우도 있으므로
        for (int i = 0; i < 10; i++) {
            dp[1][i] = 1L; // 1개 짜리 수에서 가질 수 있는 경우의 수는 각각 1가지
        }

        long result = 0;

        for (int i = 1; i < 10; i++) {
            result += makeStair(N, i); // N개의 길이를 갖는 수에서 i로 시작하는 계단수의 갯수
        }
        System.out.println(result % MOD);

    }

    private static long makeStair(int n, int i) {
        if (dp[n][i] != null) return dp[n][i]; // 계단수의 개수가 이전에 계산되었다면 반복 연산 X

        /*
        재귀 함수) N개의 계단수의 경우의 수는 N-1개의 계단수를 통해 얻을 수 있다. - Optimal Substructure
         */
        // base case : (n == 1) main 함수에서 정의했다고 가정
        if (n == 1) return dp[n][i];
        if (i == 0){
            dp[n][i] = makeStair(n - 1, 1) % MOD; // 0 다음에 올 수 있는 수는 1밖에 없음
        } else if (i == 9) {
            dp[n][i] = makeStair(n - 1, 8) % MOD; // 9 다음에 올 수 있는 수는 8밖에 없음
        } else {
            dp[n][i] = (makeStair(n - 1, i + 1) + makeStair(n - 1, i - 1)) % MOD;
        }

        return dp[n][i];
    }


}

• makeStair(int N, int i) 함수의 경우 N개의 길이에 i 번째로 시작하는 계단수의 개수를 구하는 함수이다.
  • 그림에서 정의한 것처럼 현재 값이 0 이거나 9 일 때는 다음 값을 특정 값으로 지정하며, 이외에는 현재 값에 +- 1을 하여 지정한다.
  • i가 1부터 9까지일 때의 계단수 개수를 다 더해야 하므로 분명 재귀함수가 중복되어 호출될 수 밖에 없다. 따라서 반복되는 연산을 막기 위해서 메모이제이션 기법을 사용하여 계산된 값은 static 타입인 dp 배열에 저장한다. 따라서 호출된 N과 i에 해당하는 dp 배열의 값이 null이 아닌 경우엔 이전에 계산된 값이 저장된 것이기 때문에 반복하여 연산을 하지 않고 저장된 값을 반환한다.
• base case의 경우, N이 1이 됐을 때 main 함수에서 저장했던 값을 (1개의 길이에서 i (1 ~ 9)로 가질 수 있는 개수는 1) 반환한다.

3. 주의할 점

• 맨처음 dp[1][i] ( N이 1일 때의 계단수 개수)을 1L로 초기화 할 때, i가 0인 경우도 초기화 해야 한다. 왜냐하면 계단수의 마지막이 0으로 끝날 수도 있기 때문이다. ex) 543210, 2343210
  따라서 dp[1][0]이 호출될 수도 있으며, 이 때 또한 마찬가지로 base case로써 1을 반환해야 하기 때문에 i가 0일 경우에도 1L로 초기화 해야 한다. 그렇지 않으면 null 값에 대해 연산을 진행하기 때문에 NullPointerException 이 발생한다.

4. Bottom - Up

• bottom up 방식의 경우에도 앞서 정의했던 점화식과 동일하게 작성하면 된다. 하지만 이 때는 Top Down 때와 숫자가 거꾸로 뒤집힌다. dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1] 이런식으로 작성되는데, i가 2부터 N까지 차례대로 값이 저장되어 마지막에 N일 때 계단수 개수가 구해진다. 따라서 j가 0인 경우는 0부터 시작하는 계단수가 아니라 0으로 끝나는 계단수를 의미한다.

 

출처 : https://st-lab.tistory.com/134 

[백준] 10844번 : 쉬운 계단 수 - JAVA [자바]