11057 오르막 수

문제

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

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

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

입력

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

출력

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

예제 입력 1

1

예제 출력 1

10

예제 입력 2

2

예제 출력 2

55

예제 입력 3

3

예제 출력 3

220

코드

import java.io.*;

public class P_11057 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

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

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

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

        bw.write(Integer.toString(sum));
        bw.flush();
    }
}

코드 설명

시간복잡도가 1초이고 브루트포스로 푼다면 9^1000이므로 1초를 넘어가게 되어서 dp로 풀었다.

dp[n]은 n자리 오르막수의 개수이다.

이 때, n자리 오르막수는 n-1자리 오르막수가 어떤 수로 끝났는지에 영향을 받는다.
n-1자리 오르막수가 0으로 끝난 수라면 n번째 자리에 0~9를 넣어 n자리 오르막수를 만들 수 있고, n-1자리 오르막수가 9로 끝났다면 n번째 자리에 9를 넣어서 n자리 오르막수를 만들 수 있다.
그래서 dp는 이차원배열이고 어떤 숫자로 끝나는지에 대한 정보를 담고 있다.

dp[i][j]는 i자리 오르막수 중 j로 끝나는 오르막 수의 개수를 의미한다.

이 때, j로 끝나는 오르막수는 i-1자리 오르막수 중에서 j이하로 끝나는 오르막수의 경우의 수와 같다.
그러므로 점화식은

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

가 된다.