[11057번] 오르막 수

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

 

아이디어

1. 끝나는 숫자와 자릿수를 기준으로 상태를 나눈다.

 

dp[i][j] = i자리 수에서 마지막 숫자가 j인 오르막 수의 개수

ex) dp[3][4]는 3자리 오르막 수 중, 마지막 숫자가 4인 경우의 개수

 

 

2. 점화식 작성

dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + ... + dp[i-1][0]

 

다시 작성하면

dp[i][j] = dp[i][j-1] + dp[i-1][j]

다음과 같이 작성할 수 있다.

 

dp[i][j-1]: 현재 자릿수에서 끝자리가 j-1인 오르막 수

dp[i-1][j]: 이전 자릿수에서 끝자리가 j인 오르막 수

 

 

3. 초기값

dp[1][j] = 1 (j = 0 ~ 9)

1자리 수는 각 숫자 하나만 있으니 개수는 1

 

 

 

4. 전체 합

정답은 dp[N][0] + dp[N][1] + ... + dp[N][9]

 

 

 

5. 정답

 

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

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


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

        for (int i = 2; i <= N; i++) {
            for (int j = 0; j <= 9; j++) {
                for (int k = 0; k <= j; k++) {
                    dp[i][j] = (dp[i][j] + dp[i-1][k]) % MOD;
                }
            }
        }

        int result = 0;
        for (int i = 0; i <= 9; i++) {
            result = (result + dp[N][i]) % MOD;
        }

        System.out.println(result);
    }
}