문제

45656이란 수를 보자.

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

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

입력

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

출력

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

예제 입력

1

2

예제 출력

9

17

풀이

인접한 모든 자리의 숫자가 1의 차이가 나야하므로 다음 단계로 넘어갈 때 마지막 자리의 숫자만 체크해주면 된다.

예를 들어 한자리 수의 경우는 0을 제외한 모든 숫자가 가능하므로 9개의 계단수가 나온다.

두자리 수부터는 이전 배열에서 자기 index +1, -1에 위치한 숫자를 더해주면 된다 (1의 차이가 나야하므로)

단 0과 9의 경우 0은 뒤에 올 숫자가 1밖에 없고 9는 8밖에 없으므로 따로 조건을 붙여준다.

또한 정답을 1,000,000,000으로 나눈 나머지가 정답이 되는데(MOD) 마지막 연산 전에 Number 최댓값을 넘어갈 수 있으므로 매 연산마다 MOD 연산을 해준다.

작성 코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "../ex.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");

const test_num = Number(input);
const MOD = 1000000000;

let dp = new Array(10).fill(1);
dp[0] = 0;

for (let i = 1; i < test_num; i++) {
  let dp_copy = [...dp];
  for (let j = 0; j < 10; j++) {
    if (j === 0) {
      dp[0] = dp_copy[1] % MOD;
    } else if (j === 9) {
      dp[9] = dp_copy[8] % MOD;
    } else {
      dp[j] = (dp_copy[j - 1] + dp_copy[j + 1]) % MOD;
    }
  }
}

console.log(dp.reduce((a, c) => (a + c) % MOD, 0));