[C++] BOJ 10844번: 쉬운 계단 수

문제 링크

문제 풀이

dp를 이용하여 문제를 해결하였다. 문제를 해결하기 위한 점화식을 세우는 데에 어려움을 겪었었고 조금 특이한 점화식을 이용하여 문제를 해결하였다.

 

f(N)이 N의 자리수인 계단수의 갯수라고 하고, g(N)(M)이 N의 자리수인 계단수 중 끝자리가 M인 수의 갯수라고 하자.

f(N) = g(N)(0)+ g(N)(1) + ... g(N)(8) + g(N)(9)라는 식과, g(N)(M) = g(N-1)(M-1) + g(N-1)(M+1) 식이 성립한다.

 

이 때에 주의해야 하는 점은 g(N)(M) = g(N-1)(M-1) + g(N-1)(M+1) 식에서 M-1과 M+1이 양수가 아닐 경우를 조심해야 한다는 것이다. 예를 들어 M=0일 경우 g(N)(0) = g(N-1)(-1) + g(N-1)(1)이지만 끝자리가 -1인 양수는 없으므로 g(N-1)(-1)의 값은 존재하지 않는다. 따라서 g(N)(0) = g(N-1)(1)이 된다.

 

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

코드

#include <bits/stdc++.h>

using namespace std;

int calculated[103][10];
int N;

void calculate(int num)
{
    if (num > N)
        return;

    if (num == 1)
    {
        for (int i = 1; i <= 9; i++)
        {
            calculated[1][i] = 1;
        }
    }
    else
    {
        for (int i = 0; i <= 9; i++)
        {
            if (i - 1 >= 0)
            {
                calculated[num][i] += calculated[num - 1][i - 1];
                calculated[num][i] %= 1000000000;
            }
            if (i + 1 <= 9)
            {
                calculated[num][i] += calculated[num - 1][i + 1];
                calculated[num][i] %= 1000000000;
            }
        }
    }

    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 %= 1000000000;
    }

    cout << result << '\n';

    return 0;
}