[백준/DP/C++] 11057번 오르막 수

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

11057번: 오르막 수

원래는 dp[n]으로만 식을 세웠었는데 예시를 적다보니 일의자리 수가 중요하다고 생각되어 일의자리 s를 추가했다

길이가 n이고 일의자리 수가 s인 오르막수의 개수는 길이가 n-1이고 일의자리수가 0부터 s까지인 오르막수의 개수를 모두 더하면 된다

저 sum함수를 너무오랜만에 써봐서 맞게 썼는지 모르겠지만
아무튼 점화식은 맨 아래처럼 만들 수 있다

#include <bits/stdc++.h>

using namespace std;
int n;
int dp[1001][10]={};
#define mod 10007;

int main(void) {
    cin >> n;

    for(int i=0; i<10; i++){
        dp[1][i] = 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][j] + dp[i-1][k])%mod;
            }
        }
    }
    int result = 0;
    for(int i=0; i<10; i++){
        result = (result + dp[n][i])%mod;
    }
    cout << result <<endl;

    return 0;
}