[백준 10844] 쉬운 계단 수 C++

문제 링크 : 백준 10844 쉬운 계단 수

문제

45656이란 수를 보자. 이 수는 인접한 모든 자리수의 차이가 1이 난다. 이런 수를 계단 수라고 한다. 세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다. N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오.(0으로 시작하는 수는 없다.)

입력

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

출력

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

입출력 예시

• 입력1 / 출력1 : 1 / 9
• 입력2 / 출력2 : 2 / 17
  

풀이

• 일일이 공책에 나열하다가 규칙을 찾고, 이를 점화식으로 만들어서 풀어야 하는 문제

• 첫번째 자리수에는 1~9가 올 수 있고 이 자리수가 만약 1이라면, 두번째 자리수는 0,2 만 올 수 있다.

• 첫번째 자리수가 9라면, 두번째 자리수에는 8만 가능.

• 두번째 자리수가 0이라면 세번째 자리수는 1만 가능. 이를 점화식으로 표현하면

• i = 0 일 때, cache[N][i] = cache[N-1][i+1]

  i = 9 일 때, cache[N][i] = cache[N-1][i+1] + cache[N-1][i+1]

  i = 나머지(1~8) 일 때, cache[N][i] = cache[N-1][i-1]

  
  

코드

#include <iostream>
#include <algorithm>
using namespace std;
#define MOD 1000000000
int cache[101][10]; //cache[자리수][둘째자리에 오는 수]

int main() {
    int n;
    cin >> n;

    int sum = 0;
    for(int i = 0; i < 10; i++) {
        cache[1][i] = 1;
    }

    for(int i = 2; i <= n; i++) {
        for(int j = 0; j < 10; j++) {
            if (j == 0)
                cache[i][0] = cache[i-1][1];
            else if(j == 9)
                cache[i][9] = cache[i-1][8];
            else
                cache[i][j] = (cache[i-1][j-1] + cache[i-1][j+1]) % MOD;
        }
    }
    for (int i = 1; i < 10; i++)
        sum = (sum + cache[n][i]) % MOD; //data type의 범위를 초과해서 이상한 값이 저장되기 때문에

    cout << sum % MOD << endl;
    return 0;
}