백준 11057번 오르막 수

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

11057번: 오르막 수

 

• 풀이

 

dp [x][y] : x자리 수에서 첫째 자리가 y일 때 오르막수가 될 수 있는 경우의 수

예를 들어, dp [2][7]일 때 2의 자리 수에서 첫째 자리가 7일 때 가질 수 있는 경우의 수를 의미한다. ( 7_ )

따라서 7,8,9로 총 3가지가 있는데 이는

dp [2][7] = dp [1][7] + dp [1][8] + dp [1][9]이다.

 

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int cnt = 0;
		
		//System.out.print("수의 길이 입력 : ");
		int N = s.nextInt();
		
		int dp[][] = new int [N][10];
		
		for(int i=0; i<10; i++) {
			dp[0][i]=1;
		}
		
		for(int j=1;j<N;j++) {
			for(int i=0; i<10; i++) {
				for(int z=i ; z<10 ; z++) {
					dp[j][i] += dp[j-1][z];	
                    dp[j][i] %= 10007;
				}
			}
		}
		
		for(int i=0;i<10;i++) {
			cnt += dp[N-1][i];
            cnt %= 10007;
		}
		
		
		System.out.print(cnt);
	}
}