알고리즘 - 백준, 11053번 오르막 수 (DP)

✅점화식 도출

길이가 2인 오르막 수는 00, 01, 02, ..., 99로 총 100개다.
길이가 3인 오르막 수는 000, 001, 002, ..., 999 중에서 인접한 자리수의 차이가 1 이상인 수만을 골라 총 220개가 됩니다.

dp[i][j] = dp[i-1][0] + dp[i-1][1] + ... + dp[i-1][j]

여기서 dp[i][j]는 길이가 i이고 마지막 자리수가 j인 오르막 수의 개수를 의미한다. 이 점화식은 길이가 i-1이고 마지막 자리수가 0에서 j까지인 모든 오르막 수의 개수를 모두 더해서 구할 수 있음을 나타낸다.

예를 들어, 길이가 2인 오르막 수를 구하려면 길이가 1인 오르막 수를 이용하여 구할 수 있다. 길이가 1인 오르막 수는 0부터 9까지의 모든 자연수이므로, 길이가 2이고 마지막 자리수가 0인 오르막 수의 개수는 길이가 1이고 마지막 자리수가 0부터 9까지인 모든 오르막 수의 개수를 더한 값과 같다.
즉, dp[2][0] = dp[1][0] + dp[1][1] + ... + dp[1][9]

위의 점화식을 이용하여 2차원 배열 dp를 채워나가면서 dp[n][0]부터 dp[n][9]까지 모든 값을 더하면 길이가 N인 오르막 수의 개수를 구할 수 있다.

길이가 1인 오르막 수.
이때, 모든 자리수의 값을 1로 초기화한다.
dp[1][0] = 1, dp[1][1] = 1, ..., dp[1][9] = 1

길이가 2인 오르막 수.
이때, 길이가 1인 오르막 수를 이용하여 구할 수 있다.
dp[2][0] = dp[1][0] + dp[1][1] + ... + dp[1][9]
dp[2][1] = dp[1][1] + dp[1][2] + ... + dp[1][9]
.
.
.
dp[2][9] = dp[1][9]

길이가 3인 오르막 수. 이때, 길이가 2인 오르막 수를 이용하여 구할 수 있다.
dp[3][0] = dp[2][0] + dp[2][1] + ... + dp[2][9]
dp[3][1] = dp[2][1] + dp[2][2] + ... + dp[2][9]
.
.
.
dp[3][9] = dp[2][9]

위의 과정을 반복하여 dp[n][0]부터 dp[n][9]까지 모든 값을 더하면 길이가 N인 오르막 수의 개수를 구할 수 있다.

✅코드

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

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[][] d = new int[n+1][10];

        for (int i = 0; i <= 9; i++) {
            d[1][i] = 1;
        }

        for (int i = 2; i <= n; i++) {
            for (int j = 0; j <= 9; j++) {
                for (int k = 0; k <= j; k++) {
                    d[i][j] += d[i-1][k];
                    d[i][j] %= 10007;
                }
            }
        }

        int answer = 0;
        for (int i = 0; i <= 9; i++) {
            answer += d[n][i];
        }

        System.out.println(answer % 10007);
        br.close();
    }
}