[1일 1알고] S1 10844 쉬운 계단 수

 

간단한 dp문제입니다.

인접한 모든 자리의 차이가 1인 수가 계단 수라면 길이가 N인 숫자 중 계단 수가 몇개 존재할 수 있을지를 찾아야합니다.

 

현재 n의 자리에서의 수가 A라면 그 다음 자리에는 A-1과 A+1의 수만 올 수 있습니다. 

만약 A가 0이라면 A+1인 1만, A가 9라면 A-1인 8만 가능할 것입니다.

---

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

    int N;
    cin >> N;
    vector<vector<long long>> dp(N, vector<long long>(10, 0));

    long long MOD = 1'000'000'000;

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

    for (int i = 1; i < N; ++i)
    {
        for (int j = 0; j <= 9; ++j)
        {
            if (j == 0)
            {
                dp[i][j] = dp[i - 1][j + 1];
            }
            else if (j == 9)
            {
                dp[i][j] = dp[i - 1][j - 1];
            }
            else
            {
                dp[i][j] = (dp[i - 1][j + 1] + dp[i - 1][j - 1]) % MOD;
            }
        }
    }

    long long result = 0;
    for (int i = 0; i <= 9; ++i)
    {
        result += dp[N - 1][i];
        result %= MOD;
    }
    cout << result;
    return 0;
}

결론적으로 코드는 위와 같이 됩니다.

---

처음에는 45556같이 1이하의 차이가 계단 수라고 착각해 틀렸었는데

문제를 꼼꼼히 읽을 필요가 있겠네요