[백준 11057번] 오르막 수(Java)

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

11057번: 오르막 수

실버 1 문제인 오르막 수 입니다.

---

풀이

1인 경우는 0, 1,2,3,4,5,6,7,8,9로 총 10가지입니다. 이것도 표로 구현해보겠습니다

i)길이가 1인 경우

0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1

ii)길이가 2인 경우

0	1	2	3	4	5	6	7	8	9
10	9	8	7	6	5	4	3	2	1

iii)길이가 3인 경우

0	1	2	3	4	5	6	7	8	9
55	45	36	28	21	15	10	6	3	1

이 표를 합치면

0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1
10	9	8	7	6	5	4	3	2	1
55	45	36	28	21	15	10	6	3	1

이를 보면 규칙이 보일것이다. 예를 들면, 맨앞에 숫자가 2이고 길이는 3자리인 오르막수의 수는 45-9=36이다. 

따라서 맨 앞에 붙을 숫자를 i, 오르막수의 길이를 n으로 하면 점화식은

dp[i][n]=dp[i][n-1]-dp[i-1][n-1] (i, n >0)
dp[i][0]= Sum(dp[i-1]) 

---

코드

import java.io.*;
import java.util.StringTokenizer;

public class ascent {
    
    
    

    public static void main(String args[]) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int n=Integer.parseInt(br.readLine());
        int [][]dp=new int[1010][1000];
        //초기 오르막 수의 개수 저장은 모두 1개씩 있다.
        for(int i=0;i<10;i++) {
        	dp[0][i]=1;
        	
        }
      
        
        
        for(int i=1;i<n;i++) {
        	//전단계의 오르막수를 전부 더한 값을 0번째 인덱스에 삽입
            //크기가 커지는 것을 막기 위해 10007의 나머지를 대입한다.
        	dp[i][0]=GetSum(dp[i-1])%10007;
	        for(int j=1; j<10;j++) {
	        	dp[i][j]=(dp[i][j-1]-dp[i-1][j-1]);
	        	//만약 범위가 초과되 음수가 나오면
	        	if (dp[i][j] < 0) {
	                dp[i][j] += 10007; // 음수를 방지하기 위해 10007을 더해줌
	            }
	        }
	        
	        
        }
        System.out.print(GetSum(dp[n-1])%10007);
    }
    //해당 길이의 오르막수를 전부 저장한다
    public static int  GetSum(int[]arr) {
    	int count=0;
    	for(int i=0;i<10;i++) {
    		count+=arr[i];
    	}
    	return count;
    }

   
}