javascript (nodeJS) 백준 2302 극장 좌석

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

로직

• 좌석은 좌,우로 이동이 가능

  • (n)개의 좌석의 경우의 수 = (n-1)개 경우의 수에서 자기 자리에 앉는 경우 + (n-2)개 경우의 수에서 왼쪽과 바꿔 앉은 경우
  • dp[n] = dp[n-1] + dp[n-2]
  • n = 1인 경우 : 1
  • n = 2인 경우 : 12 / 21
  • n = 3인 경우 : 2인 경우(12 / 21)에서 3을 자기 자리에 앉는 경우 + 1인 경우(1)에서 왼쪽과 바꿔 앉는 경우
  • 즉 (123 / 213) + (132)로 3가지

• vip 좌석은 고정

  • N이 5, vip 좌석이 3이라고 가정
  • 3을 기준으로 왼쪽 두칸(1,2)과 오른쪽 두칸(4,5)가 자유롭게 좌석이 변경 가능
  • 왼쪽 두칸을 배열하는 경우의 수(dp[2])와 오른쪽 두칸의 배열하는 경우의 수(dp[2])의 곱이 답이 됨

const solution = (N,M,vips) =>{
    const dp = new Array(N+1).fill(1);
    for (let idx = 2; idx<=N; idx++){
        dp[idx] = dp[idx-1] + dp[idx-2];
    }
    let answer = 1;
    let vipIdx = 0;
    for (let i=0; i<M; i++){
        const vip = vips[i];
        answer *= dp[vip-vipIdx-1];
        vipIdx = vip;
    }
    answer *= dp[N-vipIdx];
    return answer;
}

const fs = require("fs");
const URI = process.platform === "linux"?"dev/stdin":"./2302.txt";
const inputs = fs.readFileSync(URI).toString().trim().split('\n').map(Number);
const N = inputs.shift();
const M = inputs.shift();
const vips = inputs;
const ans = solution(N,M,vips);
console.log(ans);
```