[백준 10844] 쉬운계단수

https://www.acmicpc.net/problem/10844

문제

45656이란 수를 보자.

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

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

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

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

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

아이디어

0의 다음 수로는 1 한개만 올 수 있다.
1-8의 다음 수로는 2개씩 올 수 있다.(8*2 = 16 개의 선택지)
9의 다음 수로는 8 한개만 올 수 있다.

오늘 다시 풀었을 때 단순하게 각 자리에 대해 순열처럼 선택지 수 곱해나가면 되는줄 알았다.
일반적으로 하나의 자리수에 대해 총 18개의 선택지가 있다(첫번째 자리는 9개, 두번째 자리는 17개)
n길이의 0~9숫자를 나타낼 수 있는 배열로 bottom up으로 과거에 풀었더라

mod 10^9를 통해 나머지만 관리하면 된다(단 , long long 써야할줄알았는데 int 써서 풀었네???)

코드

bottom up 방식을 상당히 좋아하는 나...
print 문을 너무 좋아하는 나....

#include<iostream>
using namespace std;

int arr[101][10];
int mod = 1000000000;
int fill_arr(int n) {
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= 9; j++) {
			if (j == 0) {
				arr[i][j] = arr[i - 1][1];
			}
			else if (j == 9) {
				arr[i][j] = arr[i - 1][8];
			}
			else {
				arr[i][j] = (arr[i - 1][j - 1] + arr[i - 1][j + 1])%mod;
			}
		}
	}
	int res = 0;

	for (int j = 1; j <= 9; j++) {
		res = (res + arr[n][j]) % mod;
	}
	return res;
}

void print_arr(int n){
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= 9; j++) {
			cout << arr[i][j] << " ";
		}
		cout << endl;
	}

}


int main() {
	int n;
	cin >> n;
	//arr[0]은 안씀
	for (int j = 0; j < 10; j++) {//0~9
		arr[1][j] = 1;
	}

	cout <<fill_arr(n)<<endl;
	//print_arr(n);
	
}