백준 11057. 오르막 수

다시 푼 문제

www.acmicpc.net/problem/11057

11057번: 오르막 수

 

예전 글: tose33.tistory.com/15

쉬운 계단수랑 비슷한 문제. tose33.tistory.com/89

 

d[n][a] : 길이가 n이고 마지막 수가 a인 오르막수의 갯수 라고 하면.

 

d[2][9] = 길이가 1이고 마지막 수가 9인 오르막수의 갯수.

마지막 숫자가 9이려면 그 전 자리의 숫자는 9이하의 숫자여야 한다. 

즉 길이가 1이고 마지막 수가 0~9인 오르막수의 갯수를 더한값.

 

d[2][9] = d[1][0] + d[1][1] + d[1][2] + ... + d[1][9]

 

#include <iostream>
using namespace std;

long long d[1001][11] = {0};

int main() {
    int n;
    cin >> n;

    for(int i = 0; i < 10; i++) d[1][i] = 1;

    for(int i = 2; i <= n; i++) {
        for(int j = 0; j <= 9; j++) {

            for(int k = 0; k <= j; k++) {
                d[i][j] += d[i-1][k] % 10007 ;
            }

        }
    }

    int ans = 0;
    for(int i = 0; i < 10; i++) ans += d[n][i];
    cout << ans % 10007;
}