백준 10844 - 쉬운 계단 수

문제 설명

45656이란 수를 보자.

이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

https://www.acmicpc.net/problem/10844

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 특정한 수의 각 자릿수가 1씩 차이나는 수를 계단수라 하고, N자리의 계단수를 구하는 것이다.

 

해당 문제는 DP를 통해 간단하게 풀 수 있다.

DP에서는 i자리 수 중 j로 끝나는 계단수의 개수를 메모이제이션한다.

예를 들어, dp[3][2]는 세 자릿수 중 2로 끝나는 계단수의 개수가 된다.

계단수를 DP로 구할 수 있는 이유는 i-1자리 계단수에 하나의 수를 추가하여 i자리 계단수를 만들 수 있기 때문이다.

이를 그림으로 나타내면 다음과 같다.

j로 끝나는 계단수의 개수는 다음과 같다.

dp[i][j] = dp[i-1][j-1]+dp[i-1][j+1]

j로 끝나는 계단수는 j-1, j+1로 끝나야 하기 때문이다.

 

이때, 0과 9는 양 끝이 하나이기 때문에 따로 구해줘야 한다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>

using namespace std;

int N;
const int DIV = 1'000'000'000;
const int MAX = 101;

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

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

    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];
        
        for (int j = 1; j <= 8; j++)
        {
            dp[i][j] += (dp[i - 1][j - 1] + dp[i - 1][j + 1]) % DIV;
        }

        dp[i][9] = dp[i - 1][8];
    }

    int result = 0;
    for (int i = 0; i < 10; i++) 
    {
        result = (result + dp[N][i]) % DIV;
    }

    cout << result << "\n";

    return 0;
}

---