문제

45656이란 수를 보자.

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

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

입력

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

출력

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

풀이

처음 문제를 읽고 문제를 이해하게 약간 어려웠다.
길이가 N인 계단 수가 총 몇 개 있는지 = N자릿수의 수 중에 계단수가 몇 개 있는지

마지막에 무슨 숫자로 끝나는지에 따라 앞자리의 경우의 수가 정해진다.
N은 2이고 마지막 숫자가 3인 경우 _3에서 앞에 올수 있는 숫자는 2나 4가 된다.
N은 3이고 마지막 숫자가 3인 경우 __ 3에서 앞에 올 수 있는 숫자는 2나 4가 되면, _23에서 앞에 올수 있는 숫자는 1이나 3이 된다.

여기서 데이터를 저장할 배열 dp는 2차원 배열로
dp[ j ][ i ] = N===j이고 마지막에 오는 숫자가 i일때 경우의 수

dp[ i ][ j ] = dp[ i - 1 ][ j + 1 ] + dp[ i - 1 ][ j - 1 ]

여기서 끝자리가 0일 경우와 9일 경우는 다른 식을 써야 하는데
끝자리가 0일 경우엔 앞자리에 1만 올수 있고, 9일 경우에는 앞자리에 8만 올 수 있기 때문이다.

코드

var fs = require('fs');
let N = +fs.readFileSync('./input.txt').toString().trim();

function solution() {
	const dp = Array.from(new Array(N + 1), () => new Array(10));
	dp[1] = [0, 1, 1, 1, 1, 1, 1, 1, 1, 1];

	for (let i = 2; i <= N; i++) {
		for (let j = 0; j <= 9; j++) {
			if (j === 0) {
				dp[i][j] = dp[i - 1][j + 1] % 1000000000;
			} else if (j === 9) {
				dp[i][j] = dp[i - 1][j - 1] % 1000000000;
			} else {
				dp[i][j] = (dp[i - 1][j + 1] + dp[i - 1][j - 1]) % 1000000000;
			}
		}
	}

	let answer = 0;
	dp[N].forEach((n) => (answer += n));

	console.log(answer % 1000000000);
}

solution();