문제

접근 방안

자릿수가 k 일때 1ㅁㅁㅁㅁ 이면
이때의 오르막수 갯수를 k_1이라 하면
k_1은 (k-1)_1+(k-1)_2+(k-1)_3+(k-1)_4+(k-1)_5+....(k-1)_9가 된다.
k_2는 (k-1)_2+(k-1)_3+(k-1)_4+(k-1)_5+....(k-1)_9
...
k_9는 (k-1)_9가 된다.
이를 모조리 합쳐주면 된다.
따라서 배열 dp는

dp[자릿수][9]
로 만들면 된다.

코드

#include <iostream>
using namespace std;

int main()
{
    int i;
    int row, col;
    row = 0; col = 0;
    int input;
    cin >> input;
    int** arry;
    arry = new int *[input];
    int y;
    for (i = 0; i < input; i++) {
        arry[i] = new int[10];
    }

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

    for (row = 1; row < input; row++) {
        for (col = 0; col < 10; col++) {
            y = 0;
            for (i = col; i < 10; i++) {
                y = (arry[row - 1][i] + y)%10007;
            }
            arry[row][col] = y;
        }
    }
    int result=0;
    for (col = 0; col < 10; col++) {
        result = (result + arry[input - 1][col]) % 10007;
    }
    cout << result;

    return 0;
}