[백준] 10844번*

💻 C++ 기반

쉬운 계단 수
https://www.acmicpc.net/problem/10844

✔️ 단순히 N자리 수를 각 자리마다 0~9까지 경우의 수를 모두 따지는 것은 시간초과
✔️ 점화식을 찾아서 메모이제이션을 해줄 필요가 있다는 것을 알 수 있음
✔️ dp값이 int형을 넘어설 수 있음

1. 테이블 정의하기
먼저 과정을 직접 생각해보자.
N = 1일 때: 1, 2, 3, 4, 5, 6, 7, 8, 9
N = 2일 때: 10, 12, 21, 23, 32, 34, 43, 45, …
N = 3일 때: 101, 102, 121, 123, 210, 212, 232, 233, …


💡 N이 늘어날 때 k(k <= N)번째 숫자는 k - 1번째 숫자를 기반으로 정해진다는 것을 알 수 있다! (그 전 자리만 보면 된다는 의미)

dp[i][j] : j번째 숫자가 i로 끝나는 계단 수


2. 점화식 찾기
i가 0일 때, dp[i][j] = dp[i + 1][j - 1]
i가 9일 때, dp[i][j] = dp[i - 1][j - 1]
그 외, dp[i][j] = dp[i + 1][j - 1] + dp[i - 1][j - 1]


3. 초기값 정하기
dp[i][1] = 1(0 < i <= 9)

#include <cstdio>

using namespace std;

int main()
{
    int N;
    scanf("%d", &N);

    long long dp[10][N + 1];

    for (int i = 0; i < 10; i++)
    {
        if (i == 0)
        {
            dp[i][1] = 0;
        }
        else
        {
            dp[i][1] = 1;
        }
    }

    //( a + b ) % c = ( a % c + b % c ) % c
    for (int j = 2; j <= N; j++)
    {
        for (int i = 0; i < 10; i++)
        {
            if (i == 0)
            {
                dp[i][j] = dp[i + 1][j - 1] % 1000000000;
            }
            else if (i == 9)
            {
                dp[i][j] = dp[i - 1][j - 1] % 1000000000;
            }
            else
            {
                dp[i][j] = (dp[i + 1][j - 1] + dp[i - 1][j - 1]) % 1000000000;
            }
        }
    }

    long long ans = 0;
    for (int i = 0; i < 10; i++)
    {
        ans += dp[i][N];
    }

    printf("%lld", ans % 1000000000);
    return 0;
}