[BOJ] C++ 10844 쉬운 계단 수 - DP 테이블링 연습하기

10844번: 쉬운 계단 수

---

문제를 분석해 보면 자릿수별로 테이블링을 해서 전의 항을 사용할 수 있을 것 같다. 일단 dp로 잡고 테이블링도 dp [k]를 k자릿수에서의 계단 수라고 설정한 뒤 점화식을 구해봤다. 분명 아래 사진처럼 k-1 자릿수를 k 자릿수 구할 때 사용할 수 있긴 한데 특이 케이스를 고려해줘야 했다. k의 값에 따라서 특수 케이스의 계단수가 달라지는 건 확실한데 그 규칙을 정확하게 파악하기 힘들어서 간단하게 다차원 배열을 사용했다.

dp [i][j]를 i자릿수에 대해 j로 시작하는 계단수로 설정하니 점화식이 보였다. 

 

j==0이면 dp [i][0] = dp [i-1][1]

j==9면 dp [i][9] = dp [i-1][8]

그 외의 케이스에서는 dp [i][j] = dp [i-1][j-1] + dp [i-1][j+1]로 점화식을 찾을 수 있었고 구현은 쉽다.

 

가장 떠올리기 쉬운 테이블링에서 문제점을 찾아 살짝 바꿔주면 되는 문제였다.

/** DP 10844 쉬운 계단 수 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

long long n;
long long dp[120][10];
const long long MOD = 1000000000;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    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++)
        {
            // dp[i][j] = i자리 j로 시작하는 계단 수 개수
            if (j != 0)
                dp[i][j] += dp[i - 1][j - 1];
            if (j != 9)
                dp[i][j] += dp[i - 1][j + 1];
            dp[i][j] %= MOD;
        }
    }

    long long ans = 0;
    for (int j = 1; j < 10; j++)
    {
        ans += dp[n][j];
        ans %= MOD;
    }
    cout << ans;
}