백준 11057번 - 오르막 수

https://www.acmicpc.net/problem/11057

전형적인 DP 문제이다.
2차원 배열을 통해 점화식을 세우면 다음과 같다.

dp[i][j] = i 번째에서 j 값의 오르막 수

위의 점화식에서 i가 1일 때 (수의 길이가 1일 때)
모든 값을 1로 지정한다.



그리고 N 번째까지 모든 값을 구하면 되는데
dp[i][j]=dp[i-1][0]+....+dp[i-1][j-1]을 통해 값을 더해준 후 10007로 나눠주면 된다.




시간 복잡도는 O(N*10^2)으로 제한 시간 내에 문제를 해결할 수 있다.
마지막에 i가 N 일 때 0부터 9까지 dp[N][j] 값을 더해주면 되는 데 
모두 더한 뒤에도 10007로 나눠주는 것을 잊지 말자
(마지막에 안 나눠줘서 fail됐다.....)

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
 
    int N;
    cin >> N;
 
    vector<vector<int>> dp(N+1,vector<int>(10,0));
    
    for (int j = 0; j < 10; j++)
        dp[1][j] = 1;
 
    for (int i = 2; i <= N; i++) {
 
        for (int j = 0; j < 10; j++) {
            for (int k = 0; k <= j; k++) {
                dp[i][j] += dp[i - 1][k];
            }
            dp[i][j] %= 10007;
        }
    }
 
    int ans = 0;
    for (int j = 0; j < 10; j++) 
        ans += dp[N][j];
    
    ans %= 10007;
    cout << ans << endl;
    return 0;
}