[DP] BOJ 11057번 - 오르막 수

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

11057번: 오르막 수

DP 연습문제다.

DP[자리수][끝수]라고 정했을 때

맨 윗줄 DP[1][0] ~ DP[1][9]는 모두 1로 선언해준다.

그 다음, DP[N][K] = DP[N-1][0] + DP[N-1][1] + ... + DP[N-1][K]와 같이 점화식을 구성해주면 된다.

 

아래는 소스코드.

 

#include <stdio.h>
#pragma warning(disable:4996)
#define div 10007
int main(){
    long long DP[1001][10];
    for (int r = 0; r <= 1000; r++){
        for (int c = 0; c <= 9; c++){
            DP[r][c] = 0;
        }
    }
    for (int c = 0; c < 10; c++) DP[1][c] = 1;
    for (int r = 1; r <= 1000; r++) DP[r][0] = 1;
    int n;
    scanf("%d", &n);
    if (n == 1){
        printf("10\n");
        return 0;
    }
    for (int r = 2; r <= 1000; r++){
        for (int c = 1; c <= 9; c++){
            for (int b_c = 0; b_c <= c; b_c++){
                DP[r][c] += DP[r - 1][b_c];
            }
            DP[r][c] %= div;
        }
    
        if (r == n){
            long long ret = 0;
            for (int c = 0; c <= 9; c++) {
                ret += DP[r][c]; // 모두 더한다음에 모듈러해준다.
            }
            printf("%lld\n", ret%div);
            break;
        }
    }
    return 0;
}