[알고리즘][DP][11057] 오르막 수

[알고리즘][DP][11057] 오르막 수

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

[풀이]

• 수의 길이 = n ( 1 <= n <= 1000 )
• 오르막의 첫 번호 = k
• n자리의 오르막의 갯수 = arr[n][k]
• arr[1][k] = 10;
• arr[2][k] = 2자리의 오르막 갯수
• arr[2][0] = arr[1][0] + arr[1][1] + arr[1][2] + arr[1][3] + ... + arr[1][8] + arr[1][9]
• arr[2][1] =               arr[1][1] + arr[1][2] + arr[1][3] + ... + arr[1][8] + arr[1][9]
• arr[2][2] =                             arr[1][2] + arr[1][3] + ... + arr[1][8] + arr[1][9]
• arr[2][3] = ..
• ..
• arr[2][8] =                                                               arr[1][8] + arr[1][9]
• arr[2][9] =                                                                             arr[1][9]

------------------------------------------------------------------------------------------------

   arr[2][k] = arr[2][0] + ... + arr[2][9]

• result %= 10007

[코드]

package algorithm_basic;
 
import java.util.Scanner;
 
public class q_11057 {
    public static long mod = 10007L;
    
    public static void main(String[] args)   {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        
        System.out.println(calc(n));
    }
 
    public static long calc(int n) {
        
        long[][] arr = new long[n+1][10];
        for(int i=0;i<10;i++) {
            arr[1][i]=1;
        }
        
        for(int i=2;i<=n;i++) {
            for(int j=0;j<10;j++) {
                arr[i][j]=0;
                for(int k=j;k<10;k++) {
                    arr[i][j] += arr[i-1][k];    
                }
                arr[i][j]%=mod;
            }
        }
        
        long result=0;
        for(int i=0;i<10;i++) {
            result += arr[n][i];
                
        }
        result %= mod;
        return result;
    }
 
}