백준 10844 쉬운 계단 수

문제 설명

🔗 백준 10844 문제 링크

45656이란 수를 보자.
이 수는 인접한 모든 자리의 차이가 1이다. 이런 수를 계단 수라고 한다.
N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구해보자. 0으로 시작하는 수는 계단수가 아니다.

문제 풀이

DP로 풀 수 있다. 우선 '0으로 시작하는 수는 계단수가 아니다'라는 조건을 고려하지 않고 생각해보자.
N = 1일 때, 0~9까지 올 수 있다.
N = 2 부터는

0 다음은 1
2 ~ 8 다음은 +1, -1인 수
9 다음은 8

3가지 경우가 올 수 있다.
여기서 나는 '다음 올 숫자'에 빠져서 좀 헤맸다.

다음 수가 아니라 이전 수에 집중해보자.
이번 단계에 1이 나오는 횟수는 이전 단계에 0이 등장한 횟수이다.
이번 단계에 2가 나오는 횟수는 이전 단계에 1이 등장한 횟수와 3이 등장한 횟수의 합이다.

즉 아래 3개의 점화식으로 나타낼 수 있다.

dp[N][0] = dp[N-1][1]
dp[N][j] = dp[N-1][j-1] + dp[N-1][j+1] // 여기서 j는 2~8
dp[N][9] = dp[N-1][8]

이제 주어진 조건에 맞게 dp[0][j]를 채운다.
dp[0][0]은 0이고 나머지 dp[0][1]~dp[0][9]는 1을 대입한다.

소스코드

#include <iostream>
#include <vector>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie();
    int n;
    const int DIV=1000000000;
    cin>>n;
    vector<vector<int>> dp(n,vector<int>(10,0));
    dp[0][0]=0;
    dp[0][1]=dp[0][2]=dp[0][3]=dp[0][4]=dp[0][5]=dp[0][6]=dp[0][7]=dp[0][8]=dp[0][9]=1;
    for(int i=1;i<n;i++){
        for(int j=0;j<10;j++){
            if(j==0){
                dp[i][j]=dp[i-1][j+1]%DIV;
            }
            else if(j==9){
                dp[i][j]=dp[i-1][j-1]%DIV;
            }
            else{
                long long tmp=dp[i-1][j+1]+dp[i-1][j-1];
                dp[i][j]=tmp%DIV;
            }
        }
    }
    long long sum=0;
    for(int i=0;i<10;i++){
        sum+=dp[n-1][i];
    }
    sum%=DIV;
    cout<<sum;

    return 0;
}