백준 쉬운 계단수 [c++]

쉬운계단수 실버1

문제

45656이란 수를 보자.

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

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

입력

첫째 줄에 N이 주어진다. N은 1보다 크거나 같고, 100보다 작거나 같은 자연수이다.

출력

첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다.

풀이

• 이전 자리수가 0일경우 다음 자리수에 1만 올 수 있고, 이전 자리수가 9일경우 다음 자리수에 8만 올 수 있다.
• 반면 그 외 1~8까지는 각각 2개씩 올 수 있다.
• 0~9까지 배열을 한 자리의 dp로 생각하고 해결.

코드

#include <iostream>
using namespace std;

int main(){

    int n;
    int dp[102][10] = {0, };
    cin >> n;

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

    for(int j = 2; j <= n; j++)
    {
        for(int i = 0; i < 10; i++){
            if(i == 0){
                dp[j][1] += dp[j-1][0] % 1000000000;
            } else if(i == 9){
                dp[j][8] += dp[j-1][9] % 1000000000;
            } else{
                dp[j][i-1] += dp[j-1][i] % 1000000000;
                dp[j][i+1] += dp[j-1][i] % 1000000000;
            }
        }
    }
    
    long long int sum = 0;
    for(int i = 0; i < 10; i++)
    {
        sum += dp[n][i];
    }

    cout << sum % 1000000000 << endl;

    return 0;
}

총평

• 1~3자리까지 트리로 그려보면 쉽게 해결가능.

• ps
• dp