[BOJ/C++] 10844 쉬운 계단 수

동적 계획법으로 문제를 해결할 수 있습니다.

$DP[i][j]$는 길이 $i$번째 계단수의 마지막 숫자가 $j$인 경우입니다.

N번째 계단 수는 N-1번째 계단 수에 영향을 받습니다.

만약 N번째 자리가 9라면 N-1번째 자리엔 8만 올 수 있습니다.

$DP[i][9] = DP[i-1][8]$

N번째 자리가 0이라면 N-1번째 자리엔 1만 올 수 있습니다

$DP[i][0] = DP[i-1][0]$

N번째 자리가 3이라면 N-1번째 자리엔 2 또는 4가 올 수 있습니다.

즉, N번째 자리가 0인 경우, 9인 경우, 그 외 경우에 따라 올 수 있는 숫자가 정해져 있습니다.

$DP[i][j] = DP[i-1][j-1] + DP[i-1][j+1]$

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

using int32 = long;
using int64 = long long;

static int DP[101][10] = {};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N;
    cin >> N;

    int MOD = 1000000000;

    for (int i = 1; i < 10; i++)
        DP[1][i] = 1;

    for(int i=2; i<=N; i++)
    {
        DP[i][0] = DP[i - 1][1] % MOD;
        DP[i][9] = DP[i - 1][8] % MOD;
	    for(int j=1; j<9; j++)
            DP[i][j] = (DP[i - 1][j - 1] + DP[i - 1][j + 1])%MOD;
    }


    int64 result = 0;

    for (int i = 0; i < 10; i++)
        result = (result + DP[N][i])%MOD;

    cout << result;

    return 0;
}