• 문제 제목: 오르막 수
• 문제 링크: https://www.acmicpc.net/problem/11057

간단한 DP 연습 문제. 오르막 수는 n번째 자리에 올 수 있는 수가 n - 1번째 자리에 올 수 있는 수로 정해진다.

k라는 수가 n번째 자리에 올 수 있는 경우의 수는 n - 1번째 자리에서 0 ~ k까지 올 수 있는 수의 합이 된다.

DP[k][n] = DP[k][n-1] + DP[k-1][n-1] + ... DP[0][n-1]

경우의 수를 셀 때에는 0번째 위치의 경우의 수를 1로 초기화해서 풀어야 함에 유의.

#include <bits/stdc++.h>
using namespace std;

int DP[10][1001];
int main() {
    int N;
    scanf("%d", &N);

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

    for(int n = 1; n <= N; ++n) {
        for(int K = 0; K < 10; ++K) { // n번째 수가 K일 때 수 세기
            int& T = DP[K][n];
            for(int k = 0; k <= K; ++k) {
                T += DP[k][n - 1];
            }
            T %= 10007;
        }
    }

    printf("%d\n", DP[9][N]);
    return 0;
}