[동적계획법 (D.P.)] 백준 11057: 오르막 수, Java

1. 접근

이 문제의 경우 각 자리가 오름차순으로 되어 있는지를 확인하여 맞다면 오르막 수라는 조건을 이용해야 했습니다.

그렇기 때문에 "백준 10844: 쉬운 계단 수" 처럼 0 ~ 9의 수를 이용하여 구하는 문제라고 생각했습니다.

2차원 배열을 선언하여 각 n 자리 수일 때마다

끝 자리 수가 0 ~ 9 인 경우를 저장하고 마지막에 다 더하는 것으로 생각했습니다.

 

끝 자리의 수를 이용하여 생각하면

0은 0 ~ 9를 만들고 1은 1 ~ 9를 만들고 ... 9는 9를 만들 수 있습니다.

그러면 이런 표를 만들 수 있습니다.

2. 해결

위의 표에서 보면 n 자리의 수의 끝 자리가 i 일 경우

n - 1 자리 수 중 i 를 만들 수 있는 수들의 개수 합을 구하면 i 의 개수가 나오게 됩니다.

그러면 결국에는 n - 1 자리 수의 i 의 개수와 n 자리 수의 i - 1 의 개수를 더 하면

i 의 개수를 구할 수 있게 되는 것입니다.

 

즉, dp[n][i] = dp [n - 1][i] + dp[n][i - 1] 의 식이 완성됩니다.

3. 코드

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

        for (int i = 0; i < 10; i++) {
            dp[1][i] = 1;
        }

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

        for (int i = 0; i < 10; i++) {
            ans = (ans + dp[n][i]) % 10007;
        }

        System.out.println(ans);
    }
}