[伯俊]11057:上り坂

質問する

問題を解く

n=1からn=3まで、以下のルールを見つけました.
n=1の場合
0 1 2 3 4 5 6 7 8 9
n=2の場合
00 01 02 03 04 .. 09
11 12 13 14 15 .. 19
...
i=nであり、端数がjである場合、端数n−1では端数がjから9までの数である.
つまり、ルールは次のようになります.
dp[i][j] = dp[i-1][j] + d[i-1][j+1] + ... + dp[i-1][9]

コード#コード#

import java.util.Scanner;

public class Main {

    final static int mod = 10007;
    static int num;

    public static void main(String[] args){

        Scanner sc = new Scanner(System.in);

        //수의 길이 입력
        num = sc.nextInt();

        //long형 배열 선언 및 초기화 dp[자리수][마지막 숫자]
        int[][] dp = new int[num+1][10];
        for(int i = 0; i < 10 ; i++){
            dp[1][i] = 1;
        }

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

        int result = 0;
        for(int i = 0 ; i < 10 ; i++){
            result += dp[num][i];
        }
        System.out.println(result%mod);

    }
}