[백준] 오르막 수 (11057번 JAVA) (!) / 401 - 다이나믹 프로그래밍 1 (연습)

[백준] 오르막 수 (11057번 JAVA) (!) / 401 - 다이나믹 프로그래밍 1 (연습)

---

[접근 방법]

* N자리의 수이고 끝자리가 K 인 오르막 수의 개수는 

"N-1 자리의 수이고 끝자리가 0~K 인 오르막 수의 개수를 모두 더한 것" 과 같다.

 

즉, N 자리수의 오르막 수의 총 개수는

N 자리수 이고 끝자리가 각각 0 부터 9 까지의 경우의 수를 모두 더한 것을 구하면 된다.

 

N이 5인 경우를 예로 들겠다.

5자리수이고 끝자리 수가 5인 오르막 수의 경우의 수를 구하는 과정이다.

4자리 수이고 끝자리 수가 0 부터 5인 각각의 경우를 모두 더한 것과 같다.

 

5자리 수의 끝자리 수가 5인 경우를 위와 같이 구했다면,

5자리 수의 오르막 수를 모두 구하기 위해선 끝자리가 0 ~ 9 인 경우를 모두 더해주면 된다.

그 모든 경우는 아래와 같다.

 

---

[JAVA 코드]

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main{

    public static void main(String[] args) throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        //  (1 ≤ N ≤ 1,000)
        int N = Integer.parseInt(br.readLine());

        int[][] DP = new int[N+1][10];
        // DP[1][0~9] = 1
        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++){

                // 앞자리 수가 j 보다 작거나 같은 k인 경우 +
                for(int k=0; k<=j; k++){
                    DP[i][j] += DP[i-1][k];
                    DP[i][j] %= 10_007;
                }
            }
        }

        // N자리 수이고 끝자리가 0 ~ 9 인 오르막 수를 모두 더하는 것
        int sum = 0;
        for(int i=0; i<10; i++){
            sum += DP[N][i];
        }

        bw.write(sum % 10_007 +"\n");
        
         
        bw.flush();
        bw.close();
    }
}