[BAEKJOON] 11507번 : 오르막수 (JAVA)

- 알고리즘 분류 : 다이나믹 프로그래밍

- 사용 언어 : JAVA

- 문제 요점

    - 점화식 dp[i][j] += dp[i-1][k]

 

소스 설명은 주석을 참고해주세요.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());

        int dp[][] = new int[N+1][10];
        for(int i = 0; i < 10; i++) {
            dp[0][i] = 1;
        }

        // 점화식 : dp[i][j] += dp[i-1][k];
        for(int i=1; i<=N; i++){
            for(int j=0; j<10; j++){
                for(int k=j; k<10; k++){
                    dp[i][j] += dp[i-1][k];
                    dp[i][j] %= 10007;
                }
            }
        }

        System.out.println(dp[N][0]);
    }
}