BOJ - 극장 좌석

Link

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

접근 방법

• 좌석 중 VIP 좌석을 기준으로 좌석 배열을 나눈 그룹에 대해 경우의 수를 계산하면 된다.
• 그룹 내 좌석의 개수에 대해 다음과 같은 규칙성을 갖는다.
  • 1개 : 1
  • 2개 : 2
  • 3개 : 3
  • 4개 : 5
  • … 피보나치 수열과 동일한 규칙성을 갖는다.
• 따라서 DP 배열을 피보나치 수열에 대한 점화식으로 초기화해주고, 결과를 계산하면 끝!

Code

let file = require("fs").readFileSync("/dev/stdin");
let input = file.toString().split("\n");

let n = Number(input[0]);
let m = Number(input[1]);

let d = new Array(50).fill(0);
d[0] = 1;
d[1] = 1;
d[2] = 2;

const dp = (x) => {
  if (d[x] != 0) return d[x];
  d[x] = dp(x - 1) + dp(x - 2);
  return d[x];
};

let arr = [];
let start = 0;
for (let i = 2; i < m + 2; i++) {
  end = Number(input[i]);
  arr.push(end - 1 - start);
  start = end;
}
arr.push(n - start);

let res = 1;
for (let x of arr) {
  res *= dp(x);
}
console.log(res);