[백준 c++] 11057 오르막 수

문제

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

오르막 수는 수의 자리가 오름차순을 이루는 수다.
인접한 수가 같아도 오름차순으로 친다.
0으로 시작할 수도 있다.

예를 들어 1111, 0234, 18999는 오르막 수다.

수의 길이 N이 주어졌을 때 오르막 수의 개수를 구하는 문제다.

풀이

dp를 이용해서 풀었다.

dp[몇 자리 수인지][마지막 자리에 온 수] = 오르막 수의 개수
dp[2][2] = 두 자리 수면서 2가 마지막에 오는 오르막 수의 개수 = 02, 12, 22

결국 dp[2][2]는 1자리 수면서 2보다 작거나 같은 수로 끝난 오르막 수들의 합이다.

dp[2][2] = dp[1][2] + dp[1][1] + dp[1][0]

이 점화식 구현한 반복문을 이용해서 풀 수 있다.

코드

#include <iostream>
using namespace std;
int n, dp[1001][11], ret;
int main()
{
    cin >> n;
    for (int i = 0; i <= 9; i++)
        dp[1][i] = 1;

    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= 9; j++)
        {
            for (int k = 0; k <= j; k++)
                dp[i][j] = (dp[i][j] + dp[i - 1][k]) % 10007;
        }
    }
    for (int i = 0; i <= 9; i++)
        ret = (ret + dp[n][i]) % 10007;
    cout << ret << "\n";
}