백준 2302 JS 풀이

구하는 값

VIP좌석을 기준으로 나눠져있는 좌석에 인원 배치하는 경우의 수

핵심 아이디어

각 그룹의 묶음의 경우의수를 곱해주면 됨

근데 이 묶음의 경우의수가 피보나치 수랑 동일함

코드

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

const n = input[0] * 1;
const cnt = input[1] * 1;

// 점화식 피보나치
const d = new Array(n).fill(0);

d[0] = 1;
d[1] = 1;

for (let i = 2; i <= n; i++) {
    d[i] = d[i - 1] + d[i - 2];
}

const pick = [0];
for (let i = 2; i < cnt + 2; i++) pick.push(input[i] * 1);
pick.push(n + 1);

let total = 1;

for (let i = 0; i <= cnt; i++) {
    total *= d[pick[i + 1] - pick[i] - 1];
}

console.log(total);