[백준 11057] 오르막 수 (DP) (C/C++) (★)

#include <iostream>
#include <algorithm>
using namespace std;
 
#define MOD 10007
 
int N;
int sum;
int dp[1010][11];
 
int solve(int cnt, int num)
{
    if(cnt == 1)
    {
        return 1;
    }
    
    if(dp[cnt][num] != 0)
    {
        return dp[cnt][num];
    }
 
    for(int i = num; i >= 0; i--)
    {
        dp[cnt][num] = (dp[cnt][num] + solve(cnt-1, i)) % MOD;    
    }
    
    return dp[cnt][num];
}
 
int main(void)
{
//    freopen("B11057_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 0; i <= 9; i++)
    {
        sum = (sum + solve(N, i)) % MOD;     
    }
    
    cout << sum;
    
    return 0;
}