[C++] BOJ 11057번: 오르막 수

문제 링크

문제 풀이

dp를 이용하여 문제를 해결하였다. 이전에 풀었던 10844번: 쉬운 계단수와 비슷한 문제이다. 코드에 차이점이 있다면 2중 for문을 사용했다는 점이다.

 

이 문제를 풀 때에 주의해야 할 점은 정답을 10007로 나눈 나머지를 출력해야 한다는 것이다.

코드

#include <bits/stdc++.h>

using namespace std;

int calculated[1003][10];
int N;

void calculate(int num)
{
    if (num > N)
        return;
    if (num == 1)
    {
        for (int i = 0; i <= 9; i++)
        {
            calculated[1][i] = 1;
        }
    }
    else
    {
        for (int i = 0; i <= 9; i++)
        {
            for (int j = i; j <= 9; j++)
            {
                calculated[num][i] += calculated[num - 1][j];
                calculated[num][i] %= 10007;
            }
        }
    }
    calculate(num + 1);
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N;

    calculate(1);

    int result = 0;
    for (int i = 0; i <= 9; i++)
    {
        result += calculated[N][i];
        result %= 10007;
    }

    cout << result << '\n';

    return 0;
}