[BOJ]11057: 오르막수 (C++)

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

11057번: 오르막 수

문제 요약

길이가 N인 오르막의 수를 10007로 나눈 나머지 출력

풀이 

길이가 2인 오르막 수를 구하는데 마지막 숫자가 9인 것을 생각해보면, 09,19,29,...99 까지 세어준다. 그런데 09,19,...89까지의 개수는 

마지막 숫자가 8의 갯수와 똑같다.

따라서 점화식은 dp[i][n] = dp[i-1][n] + dp[i][n-1] 이 되어야 한다. 

위의 점화식에서 열의 크기는 길이를 뜻하므로 답을 구할 땐 result += dp[N][i]로 구해준다.

 

정답

#include <iostream>

using namespace std;
#define mod 10007

int dp[1001][10] = {
    0,
};
int main()
{
    int n;
    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++) {
            if (j == 0) {
                dp[i][0] = 1;
                continue;
            }

            dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]);
            dp[i][j] %= mod;
        }
    }

    int result = 0;
    for (int i = 0; i < 10; i++)
        result += dp[n][i];

    cout << result % mod;

    return 0;
}