백준 11057번 c++ 풀이

갈수록 기계적으로 풀게 되는 dp 초급 문제..

#include <iostream>
#include <algorithm>
#include <queue>
#include <climits>
#include <string>
#include <map>
using namespace std;

int dp[1001][10];
int func(int n, int radix){
    if (dp[n][radix] != -1){
        return dp[n][radix];
    }
    dp[n][radix] = 0;
    for (auto i =0; i<= radix; i++){
        dp[n][radix] = (dp[n][radix] + func(n-1, i)) % 10007;
    }
    return dp[n][radix];
}
int main(){
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    int n;
    cin >> n;
    for (auto i=1; i<=n; i++){
        for (auto j=0; j<10; j++){
            dp[i][j]=-1;
        }

    }
    for (auto j=0; j<10; j++){
        dp[1][j]=1;
    }
    int sum = 0;
    for (auto j=0; j<10; j++){
        sum = (sum + func(n,j)) % 10007;
    }
    cout << sum;

    return 0;
}