BOJ 11057 오르막 수

boj 11057 오르막 수

길이가 N인 오르막 수의 경우의 수를 어떻게 나눌까. boj 10844 쉬운 계단 수 문제와 비슷하게 끝 자리 수가 0-9 중에 하나인 것은 자명하고, 그러므로 끝 자리 수의 경우로 나누었다.

끝 자리 수가 0이면, 앞에 올 수 있는 수는 0
끝 자리 수가 1이면, 앞에 올 수 있는 수는 0, 1
끝 자리 수가 2이면, 앞에 올 수 있는 수는 0, 1, 2
.
.
.
끝 자리 수가 9이면, 앞에 올 수 있는 수는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

즉, 길이가 N이고 끝 자리 수가 1인 경우, 앞에 길이가 N-1이고 끝자리 수가 0 이거나 1인 오르막 수가 올 수 있다는 의미이다.
테이블로 D[i][j]는 길이가 i이고 끝 자리 수가 j인 오르막 수의 갯수로 정의하고 코드를 구현했다.

#include <iostream>
using namespace std;

int n;
long long ans;
int D[1005][15];

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    for (int i = 0; i <= 9; i++) D[1][i] = 1;

    for (int i = 2; i <= n; i++)
    {
        for (int j = 0; j <= 9; j++)
        {
            for (int k = 0; k <= j; k++)
                D[i][j] += (D[i - 1][k]) % 10007;
        }
    }
    for (int i = 0; i <= 9; i++) ans += D[n][i];

    cout << ans % 10007;
}

DP 문제에서 문제에서 지정해준 수로 나눈 나머지를 출력하라는 문제가 종종 보인다. 갯수가 너무 많아져 범위를 초과하는 경우를 방지하고자 하는 이유일 것이다. DP에서 쓸만한 나머지와 관련된 성질을 하나 정리했다.

(A + B) % M = (A % M + B % M) % M