[백준] 11057 : 오르막 수 JAVA 풀이

만약 N = 2라면

첫 번째 자리에 0이 오면 두 번째 자리에는 0부터 9까지 총 10개가 올 수 있다.

첫 번째 자리에 1이 오면 두 번째 자리에는 1부터 9까지 총 9개가 올 수 있다.

이런 식으로 생각해보면 두 자릿수인 오르막 수는 총 55개가 된다. (10+9+....+3+2+1)

 

만약 N = 3이라면

첫 번째 자리가 0이면 뒤에 두자릿수는 전에 찾았던 두 자릿수의 모든 오르막 수가 되니 55개가 올 수 있다.

결국 0부터 9까지의 숫자로 만들 수 있는 오르막 수는 이전 N-1 자릿수의 j부터 9까지의 값의 합과 같다.

 

표를 그려보면 더 쉽게 이해할 수 있다.

	0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1	1
2	10	9	8	7	6	5	4	3	2	1
3	55	45	...

 

import java.io.*;
public class Main{
	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];
        
        // 한자리수일 때 i로 끝나는 오르막수의 개수를 초기화
        for(int i=0;i<10;i++) dp[1][i] = 1;
        
        for(int i=2;i<=N;i++)
        	for(int j=0;j<10;j++)
        		for(int k=j;k<10;k++) {
                	// 이전 행의 
        			dp[i][j] += dp[i-1][k];
                    // int의 범위를 넘지 않도록 덧셈 연산 후 모듈러 연산을 해줌
        			dp[i][j] %= 10007;
        		}
        int sum = 0;
        // N번째 행의 모든 값을 더한 것이 N자리수 오르막수의 개수
		for(int val : dp[N]) sum+=val;
        // 마찬가지로 int 범위를 넘지 않도록 모듈러 연산해서 출력해줌
		System.out.println(sum % 10007);
    }
}