[백준] 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);

    }
}