[Java] 백준 11057 : 오르막 수

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

11057번: 오르막 수

---

 

	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

표에서 세로는 자릿수(N)를 의미한다. 가로는 우리가 이용할 수 있는 숫자(i)이다. 

채워진 값은 i를 가지고 N자리수를 만들었을 때의 개수이다. 

 

예를 들면 

N=1 이면, 0,1,2,3,4,5,6,7,8,9를 만들 수 있다. 

N=2 이면,

0으로는 00,01,02,03,04,05,06,07,08,09  

1로는 12,13,14,15,16,17,18,19 

2로는 23,24,25,26,27,28,29

..

9로는 99를 만들 수 있다. 

 

이런 식으로 값을 갖게 된다. 

이 값들의 규칙을 찾아보면, N자릿수의 i번 값은 N-1 자릿수의 i~9까지의 값을 모두 더한 값이다.

즉,

두자릿수 0으로 시작하는 수는 한 자릿수의 0~9까지의 합인 10개 이고,

두 자릿수 1로 시작하는 수는 한 자릿수의 1~9까지의 합인 9개이다. 

이를 점화식으로 나타내면 dp[i][j] += dp [i-1][k];이고 이를 i~9까지 반복하게 하면 된다. 

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

 

그리고 길이가 N인 오르막 수의 개수는 dp[N][0]에서 그 값을 찾을 수도 있지만 나는 결과를 출력할 때 dp [N]의 합을 구해서 출력했다.

 

---

import java.util.*;
public class Main {
		
	static int N;
	static int[][] dp;
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		N=Integer.parseInt(sc.next());	//테스트 케이스
		dp= new int[N][10];
		
		for(int i=0;i<10;i++) {
			dp[0][i]=1;
		}
		

		for(int i = 1; i < N; i++) {	//자리수만큼 반복
			for(int j = 0; j < 10; j++) {	//i자리수의 0~9
				for(int k = j; k < 10; k++) {	
					dp[i][j] += dp[i-1][k];
					dp[i][j] %= 10007;
				}
			}
		}
		
		System.out.println(Arrays.stream(dp[N-1]).sum()%10007);
		
	}// main()
	
}// class Main