백준 다시 해석] 10844 : 쉬운 계단 수

10844번: 쉬운 계단 수

 

문제  : 

45656이란 수를 보자.

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

세준이는 수의 길이가 N인 계단 수가 몇 개 있는지 궁금해졌다.

N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.)

 

 

입력  : 

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

 

 

출력  : 

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

 

 

 

 

   

수정) 1~9까지가 아니라 0부터 9까지입니다.

 

 

 

 

 

#include <iostream>
using namespace std;

#define MOD 1000000000


int dp[101][10];
int N;
long long sum;

int main() {
	
	cin >> N;
	
	for(int i = 1; i < 10; i++){
		dp[1][i] = 1;
	}
	
	// i < N으로 해서 결과값이 안 나옴.
	for(int i = 2; i < N + 1; i++){
		for(int j = 0; j < 10; j++){
			if(j == 0){
				dp[i][j] = dp[i - 1][j + 1];
			}
			else if(j == 9){
				dp[i][j] = dp[i - 1][j - 1];
			}
			else{
				dp[i][j] = (dp[i - 1][j -1] + dp[i - 1][j + 1]) % MOD;
			}
		}
	}
	
    // MOD 잊지말기
	for(int i = 0; i < 10; i++){
		sum += dp[N][i] % MOD; 
	}
	
	cout << sum % MOD;
	
	return 0;
}