[PS] 백준 11057번 오르막 수 - DP

문제

예제

풀이

이 문제는 쉬운 계단 수 문제의 연장선이다.

주의할 점은 계단 수와 달리 숫자를 0부터 시작할 수 있다.

똑같이 dp[자릿수길이][마지막자릿수] 이차원배열을 사용하였고, 다음 필기와 같은 규칙성을 찾을 수 있다.

 

 

따라서 도출되는 점화식 dp[n][i] = dp[n-1][0] + dp[n-1][1] + dp[n-1][2] + ... + dp[n-1][i]를 사용하여 푼다.

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    final static long mod = 10007;

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        long[][] dp = new long[N+1][10];

        //자릿수가 1일 때는 자릿값이 모두 1
        for(int i=0;i<10;i++) {
            dp[1][i] = 1;
        }

        //자릿수가 2일 때부터  ~ N일 때까지 탐색
        for(int i=2; i<=N; i++) {
            for(int last=0; last<10; last++) {
                for(int k=0; k<=last; k++) { //dp[i-1][0] ~ dp[i-1][last]까지 다 더한다

                    dp[i][last] += dp[i-1][k];//i-1의 경우의 수 누적합
                    dp[i][last] %= mod;
                }
            }
        }

        long result = 0;

        for(int i=0; i<10; i++) {
            result += dp[N][i];//자릿수가 N인 경우의 수 모두 더한다
        }

        System.out.println(result % mod);
    }
}