[Baekjoon Online Judge] 11057번: 오르막 수

11057번: 오르막 수

요구사항

 - 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

 - 수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성한다. 수는 0으로 시작할 수 있다.

입력

 - 첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

출력

 - 첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

---

숫자의 자리수와 각 자리수의 끝 자리를 저장하는 이차배열을 dp 테이블로 사용한다. 만약, 자신의 숫자와 같거나 큰 수가 오면 무조건 오르막 수 인 것을 보장하게 된다.

 

예를들어 OO5 (O은 공백이라고 가정한다.) 라는 3자리 수는 O1, O2, O3, O4, O5가 오는 경우 각각 O15, O25, O35, O45, O55는 오르막 수가 된다.

 

즉 정리하면 이전 자리 수 중 새롭게 붙는 숫자 보다 작거나 같은 것들을 모두 더해주면 된다.

 

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

public class Baekjoon11057 {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bufferedReader.readLine());
        int[][] dp = new int[n + 1][10];

        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= 9; j++) {
                if (i == 1) {
                    dp[i][j] = 1;
                    continue;
                }

                for (int k = 0; k <= j; k++) {
                    // 새롭게 추가된 j는 j보다 작거나 같은 k를 모두 더해준다.
                    dp[i][j] += dp[i - 1][k]; 
                }
                dp[i][j] %= 10007;
            }
        }

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

        System.out.println(sum % 10007);

        bufferedReader.close();
    }
}