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

문제 링크

11057번: 오르막 수

풀이

DP로 푸는 문제
1자리 수일 때는 0~9까지 10개
2자리 수일 때는 00~09, 11~19 ~ 99해서 55개이다.
규칙은 n길이의 맨 첫번째 숫자가 만약 5라고 한다면 n-1길이의 숫자에서 55~99까지의 개수가 5로 시작하는 오르막 수의 개수일 것이다.

3 길이의 5로 시작하는 오르막 수를 구한다면,
555~559, 566~569, ..., 588~589, 599가 될 것이다. 해당 범위로 자른 이유는 n-1길이에서 55~59의 개수, 66~69의 개수 .. 를 구했을 것이기 때문이다.

점화식은 arr[n][i] = arr[n-1][i] + arr[n][j+1] (누적합으로 구해줄 것임)

코드

#include <iostream>
#include <vector>
#define mod 10007
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    vector<vector<int>> arr(n + 1, vector<int>(10));
    for (int i = 0; i < 10; i++)
    {
        arr[0][i] = 1;
    }
    for (int i = 1; i <= n; i++)
    {
        arr[i][9] = 1;
        for (int j = 8; j >= 0; j--)
        {
            arr[i][j] = ((arr[i][j + 1] % mod) + (arr[i - 1][j] % mod)) % mod;
        }
    }
    cout << arr[n][0];
}