백준 11057: 오르막 수

다이나믹 프로그래밍을 이용해서 푸는 문제 자리 수가 i이고 자리 수의 마지막 수가 j라고 하면 d[i][j] 라는 식으로 표현하고

이는 d[i][j] += d[i -1][k] (0 <= k<= j) 점화식으로 확장 될 수 있다. 잘 생각해보면 예를들어 마지막 수가 8이면 마지막 수가 0부터 8까지 전 자리 수의 개수를 더해주면 된다. 3중 for문이라 좀 당황했는데 n에 따라 변하지는 않으므로 복잡도는 O(n)이라고 볼 수 있을 것 같다.

#include <iostream>
using namespace std;
int input = 0;
long long d[1050][15];
int main()
{
    cin >> input;
    for(int i = 0;i < 10; ++i)
        d[1][i] = 1;
    for(int i = 2; i <= input; ++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] %= 10007;
            }
        }
    }
    long long ans = 0;
    for(int i = 0;i < 10; ++i)
    {
        ans += d[input][i];
        ans %= 10007;
    }
    cout << ans;
    return 0;
}