kingsubin

import java.io.*;

public class boj_11057 {
    static int[][] dp;
    static final int mod = 10007;
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        int n = Integer.parseInt(br.readLine());
        dp = new int[n+1][10];

        for (int i = 0; i <= 9; 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-1][k];
                    dp[i][j] %= mod;
                }
            }
        }

        long ans = 0;
        for (int i = 0; i <= 9; i++) {
            ans += dp[n][i];
        }
        System.out.println(ans % mod);
    }
}

 

- 마지막 부분에 올 수 있는 수는 ? -> 0~9 까지이고 변수 L로 생각

- 그렇다면 앞에 올 수 있는 경우의 수는 ? -> L보다 같거나 작은 값들

- dp[n][L] :: 길이가 n인 수에서 L로 끝나는 경우의 수

- dp[n][L] = sigma( dp[n-1][K] ) :: 0 <= K <= L

- 이 점화식으로 dp를 채우고 정답은 sigma( dp[n][0] ~ dp[n][9] ) 이다 .