[백준] DP 10844번: 쉬운 계단 수

문제

45656이란 수를 보자.

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

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

입력

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

출력

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

Approach

사용 알고리즘: dp

• 일단 길이가 1인 계단수는 1 ~ 9 이렇게 있다
• 길이가 2부터 보텀업 진행
• n - 1 계단수 마지막자리랑 추가되는 숫자의 차이가 1이어야하기 때문에 두가지 경우가 있다. 마지막숫자보다 +1 이거나 -1 이거나
• 점화식: d[n] = d[n - 1] + d[j - 1] 아니면 d[n - 1] + d[j + 1] (이때 만약 j - 1이나 j + 1이 0부터 9사이가 아니면 무시한다

Source Code

#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <string>
#include <sstream>
#include <math.h>
#include <cstring>
using namespace std;



int main()
{
    long long int d[101][10];
    
    int n;
    cin >> n;
    
    // 길이가 1인 계단수는 총 1개 (1 ~ 9)
    for (int i = 1; i <= 9; i++)
    {
        d[1][i] = 1;
    }
    
    // 보텀업 진행
    for (int i = 2; i <= n; i++)
    {
        for (int j = 0; j <= 9; j++)
        {
            d[i][j] = 0; // 초기화
            if (j - 1 >= 0) // 추가될 숫자가 0보다 작지 않은 경우 
                d[i][j] += d[i - 1][j - 1];
            if (j + 1 <= 9) // 추가될 숫자가 9보다 크지 않은 경우 
                d[i][j] += d[i - 1][j + 1];
            d[i][j] %= 1000000000; // mod해주기
        }
        
       
    }
    
    long long ans = 0;
    for (int i = 0; i <= 9; i++)
    {
        ans += d[n][i]; // 계단수 총 갯수 구하기 
    }
    
    cout << (ans % 1000000000) << endl; // 답안 출력
    
    
    return 0;
}