[Algorithm] DP 백준 11057 오르막 수 | C++

※ 11057 오르막 수

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

11057번: 오르막 수

---

문제 해결 TIP

• 수의 길이가 N일 때의 오르막 수의 개수를 한 번에 구하지 말고 이전에 구한 값을 활용해보자.
• 숫자의 길이와 일의 자리 수를 기준으로 오르막 수의 개수를 계속 저장하고, 활용하자. -> DP 알고리즘

문제 해결 풀이

1. <점화식> dp[i][j] = 수의 길이가 i이고, 일의 자리 수가 j인 오르막 수의 개수 = (j보다 작은 수 or j와 같은 수) + j를 하면 오르막 수가 됨 = [j보다 작은 수로 끝나는 길이 i-1인 오르막 수 개수] + [j로 끝나는 길이 i-1인 오르막 수 개수] (이때, j보다 작은 수로 끝나고 길이가 i-1인 오르막 수의 개수는 dp[i][j-1]과 같음)
2. 따라서 dp[i][j] = dp[i][j-1] + dp[i-1][j]

---

#include <iostream>
#include <vector>

using namespace std;
const int MOD = 10007;

//길이 N에서 일의 자리 수가 0 ~ 9인 오르막 수 모두 더하는 함수
int sumLastCnt(vector<int> &arr) {
    int ans = 0;
    for (int i = 0; i < arr.size(); i++) {
        ans += arr[i];
        ans %= MOD;
    }
    return ans;
}

int solution(int n) {
    vector<vector<int>> dp(n + 1, vector<int>(10, 1));

    for (int i = 2; i <= n; i++) {
        for (int j = 1; j < 10; j++) {
            dp[i][j] = dp[i][j - 1] + dp[i - 1][j];
            dp[i][j] %= MOD;
        }
    }
    return sumLastCnt(dp[n]);
}

int main() {
    int n;

    //입력
    cin >> n;

    //연산 & 출력
    cout << solution(n);
    return 0;
}