문제

image.png

image.png

풀이

  • 오르막 수는, 수의 자리가 오름차순을 이루는 수를 의미한다.
  • 앞자리와 같은 수도 오름차순으로 생각한다.
  1. n = 1

    1,2,3,4,5,6,7,8,9

    dp[1][1] = 1
    dp[1][2] = 1
    dp[1][3] = 1
    dp[1][4] = 1
    dp[1][5] = 1
    dp[1][6] = 1
    dp[1][7] = 1
    dp[1][8] = 1
    dp[1][9] = 1

  2. n = 2

    11,12,13,14,15,16,17,18,19
    22,23,24,25,26,27,28,29
    33,34,35,36,37,38,39
    44,45,46,47,48,49
    66,56,57,58,59
    66,67,68,69
    77,78,79
    88,89
    99

    dp[2][1] = 9
    dp[2][2] = 1
    dp[2][3] = 1
    dp[2][4] = 1
    dp[2][5] = 1
    dp[2][6] = 1
    dp[2][7] = 1
    dp[2][8] = 1
    dp[2][9] = 1

dp[1] = 9
dp[2] = 55

코드

#include <iostream>
using namespace std;
long long d[1001][10];
long long mod = 10007;
int main() {
    int n;
    cin >> n;
    for (int i=0; i<=9; 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];
                d[i][j] %= mod;
            }
        }
    }
    long long ans = 0;
    for (int i=0; i<10; i++) {
        ans  += d[n][i];
    }
    ans %= mod;
    cout << ans << '\n';
    return 0;
}