백준 11057 : 오르막 수

문제 링크입니다 https://www.acmicpc.net/problem/11057

11057번: 오르막 수

길이가 N인 수 중에서 오름차순을 이루는 수의 개수를 구하는 문제였습니다. 점화식을 세우기 위해 "D[N][K] : 길이가 N이고 마지막에 오는 수가 K인 오르막 수의 개수"라고 한다면, K의 앞에 올 수 있는 수는 K보다 작거나 같은 모든 수입니다(문제에서 수는 0으로도 시작할 수 있다고 했습니다).

 

그러므로,

[1] D[N-1][K-0] : 길이가 N-1이고 마지막에 오는 수가 K-0인 오르막 수의 개수

[2] D[N-1][K-1] : 길이가 N-1이고 마지막에 오는 수가 K-1인 오르막 수의 개수

[3] D[N-1][K-2] : 길이가 N-1이고 마지막에 오는 수가 K-2인 오르막 수의 개수

...

[K] D[N-1][K-K] : 길이가 N-1이고 마지막에 오는 수가 K-K인 오르막 수의 개수 입니다.

 

즉, "(for K = 0 ~ K), D[N][K] = D[N-1][K]"라는 점화식을 얻게 됩니다. 문제 구현 방법은 다음과 같습니다.

 

 

[소스코드]

 

#include<cstdio>
 
// dp[n][k] : 길이가 n이고, 마지막에 온 수가 k인 오르막 수의 개수
int n, m = 10007, dp[1001][10], ans;
 
int main(void) {
    
    // 한 자릿수의 오르막 수의 개수는 1로 저장합니다
    for (int i = 0; i <= 9; i++) dp[1][i] = 1;
 
    scanf("%d", &n);
 
    // 길이가 2부터 n까지인 수들의 오르막 수의 개수를 결정합니다
    for (int i = 2; i <= n; i++)
 
        // 맨 뒤에 오는 수는 0부터 9까지 가능하고
        for (int j = 0; j <= 9; j++)
 
            // 그 바로 앞에 오는 수는 0부터 j까지 가능합니다
            // (오르막 수 이므로 j보다 작거나 같아야 합니다)
            for (int k = 0; k <= j; k++) {
                dp[i][j] += dp[i - 1][k];
                dp[i][j] %= m;
            }
    
    // 길이가 n이고 마지막에 온 수가 i인 모든 오르막 수를 더해줍니다
    for (int i = 0; i <= 9; i++) ans += dp[n][i];
    printf("%d", ans % m);
    return 0;
}