백준 1309번: 동물원 - javascript

백준 1309번: 동물원

문제 설명

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

입력

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

출력

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

접근

처음에는 N이 1인경우, 2인경우, 3인경우를 구해서 그들 간의 점화식을 찾으려했다.(사실 그게 정답 맞다.)
그런데 문제는 그게 dp[i] = dp[i-2] + dp[i-1]x2 라는 공식이였고, 그 공식을 간단하게 i, i-1, -2번째 항들 간의 관계를 찾을수 없었던 나는 다른 방법을 찾기 시작했다..
사자가 첫째 줄에서 없을때, 좌측에 있을때, 우측에 있을때로 구분해서 출력해보았다.

그 결과 위와 같은 표를 얻을수 있었는데,i번째의 공백은 이전 i-1항의 모든 결과값을 합한 값이고, 각 i번째의 좌측, 우측 항들은 각자 i-1항에서 자신들의 라인을 제외한 나머지 2곳의 합인 규칙을 찾을 수 있었다.

arr[i][공백] = arr[i-1][공백] + arr[i-1][좌측] + arr[i-1][우측]
arr[i][좌측] = arr[i-1][공백] + arr[i-1][우측]
arr[i][우측] = arr[i-1][공백0] + arr[i-1][좌측]

정답 코드

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 () {
  // 답안 작성
  let n = input[0]*1;
  let arr = [];
  for(let i = 0;i<n+1;i++){
    arr.push([0,0,0])
  }
  let answer = cage(n, arr);
  console.log(answer)
  process.exit();
});

function cage(n, arr){
  arr[0][0] = 1;
  arr[0][1] = 1;
  arr[0][2] = 1;  
  for(let i=1;i<=n;i++){    
    arr[i][0] = (arr[i-1][0] + arr[i-1][1] + arr[i-1][2])%9901;
    arr[i][1] = (arr[i-1][0] + arr[i-1][2])%9901;
    arr[i][2] = (arr[i-1][0] + arr[i-1][1])%9901;    
  }
  return arr[n][0];
}