[백준 11057] 오르막 수

 

 

길이가 1일때 10(1+1+1+1+...+1)

길이가 2일때 55(1+2+3+4+...+10)

길이가 3일때 220(1+3+6+10+...+55) 이다.

 

dp[2][1] = dp[1][1]

dp[2][2] = dp[1][1] + dp[1][2]

dp[2][3] = dp[1][1] + dp[1][2] + dp[1][3] ......

 

을 바탕으로 점화식을 세워 풀이한다.

 

각 인덱스를 더하면 자료형의 범위를 초과할 수 있으므로 매 연산마다 10007 로 나누어주고

마지막에도 나누어주면 되겠다.

 

 

public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int n = sc.nextInt();
        
        int dp[][] = new int[1001][10];
        
        for(int i=0; i<10; i++) dp[1][i] = 1;
        
        for(int i=2; i<n+1; i++) {
            for(int j=0; j<10; j++) {
                for(int k=0; k<=j; k++) {
                    dp[i][j] = (dp[i][j] + dp[i-1][k]) % 10007;
                }
            }
        }
        
        int sum = 0;
        for(int i=0; i<10; i++)
            sum = (sum + dp[n][i]) % 10007;
        
        System.out.println(sum);
    }
}