백준 10844번: 쉬운 계단 수 - javascript

백준 10844번: 쉬운 계단 수

문제 설명

45656이란 수를 보자.

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

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

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

입력

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

출력

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

접근

먼저, N의 길이가 1인 경우 1부터 9까지 수를 가진 길이 9의 배열이 나온다. 그 다음 N의 길이가 2일 경우 나올 수 있는 경우의 수는 10, 12, 21, 23 …. 89, 98 이다. 그 다음 N의 길이가 3인 경우는 101, 121, 123 … 898, 987, 989가 된다.

처음에는 N 과 N-1, N-2의 상관관계를 찾아보려 했는데 그건 아니었던 것 같다. 그다음으로는 연속된 패턴을 찾으려 했지만 0과 9의 다음 계단수는 각각 1과 8 하나씩만 존재 하므로 패턴이 계속 변화한다.

그런데 이때 0과 9 때문이라면 0부터 9까지 각각의 수의 패턴은 어떨까? 하는 생각을 하게 되었다. 0이 나오게 되는 경우는 무조건 앞자리가 1인 경우이다. 9가 나오게 되는 경우도 무조건 앞자리가 8인 경우다. 나머지 자연수 n은 자신의 앞자리가 n-1이거나 n+1인 경우에만 존재하게 된다.

N	0	1	2	3	4	5	6	7	8	9
1	0	1	1	1	1	1	1	1	1	1
2	1	1	2	2	2	2	2	2	2	1
3	1	3	3	4	4	4	4	4	3	2

… 이런식으로 각 수에 대한 규칙을 찾을 수있다.

const readline = require('readline');
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});
let input = [];
rl.on('line', function (line) {
  input.push(line)
})
  .on('close', async function () {
  // 답안 작성
  const arr = Array.from({length:input[0]+1},()=>[0,0,0,0,0,0,0,0,0,0])  
  arr[0] = [0,1,1,1,1,1,1,1,1,1];  
  let answer = stair_num(input[0], arr);  
  console.log(answer%1000000000)  
  process.exit();
});

//n자리 계단수의 경우의 수
function stair_num(n, arr){
  if(n==1){
    return 9;
  }
  for(let i = 1;i<n;i++){
    arr[i][0] = arr[i-1][1];
    arr[i][9] = arr[i-1][8];
    for(let j = 1;j<9;j++){
      arr[i][j] = (arr[i-1][j-1] + arr[i-1][j+1])%1000000000;
    }
  }
  let sum = arr[n-1].reduce((acc,cur)=>{    
    return (acc+cur*1)%1000000000
  },0);
  return sum;
}