[伯俊]11057号上り坂水-Java,Java

難易度

銀色.

質問する

https://www.acmicpc.net/problem/11057

に答える

定義

表

D[i]=数の長さがiの場合、上り坂数の個数

点火式

を探しています
N=1が1桁の場合、0から9が10種類
N=2桁です.
0で始まると10種類あります
1から10種類
2から始まると、9種類あります
3から始まると、8種類あります
...
9から始まった時、あることがありました.
合計55種類
すなわち、0から9までの数字(j)毎に発生する上り坂数は、前桁N−1のjから最後の9までの総和である.

初期値

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

コード#コード#

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

// 11057번 오르막 수
public class boj_4_11057 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        int[][] dp = new int[n + 1][10];

        for (int i = 0; i < 10; i++) {
            dp[0][i] = 1;

        }

        for (int i = 1; i < n + 1; i++) {
            for (int j = 0; j < 10; j++) {
                for (int k = j; k < 10; k++) {
                    dp[i][j] += dp[i - 1][k];
                    dp[i][j] %= 10007;
                }
            }
        }
        System.out.println(dp[n][0]);

    }
}