[알고리즘] 백준 11057 오르막수

 

import java.util.Scanner;

public class BJ_11057 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        int[][] dp = new int[n + 1][10];

        dp[1][0] = 10;

        if (n >= 2) {
            for (int i = 10; i >= 1; i--) {
                dp[2][i - 1] = 11 - i;
            }

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

        // print
        int answer = 0;

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

        System.out.println(answer);

    }
}