백준 2302 < 극장 좌석 > JavaScript

📍문제 링크

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

2302번: 극장 좌석

 

📍알고리즘 분류

- 다이나믹 프로그래밍

 

📍문제 풀이

1️⃣피보나치 수열임을 파악하기

- 1 2 3 4 5.. N 의 N명이 양 옆으로만 움직일 수 있을 때 가짓수는 피보나치 수열 fib(N)과 일치

- 즉, fib(N) = fib(N - 2) + fib(N - 1)

 

그 이유는,

N번째 사람이 N 자리일 수 있고, N-1 자리일 수 있는데,

i) N 자리이면 N-1명의 가짓수인 fib(N-1)에 해당하고

ii) N-1 자리이면 N-2명의 가짓수인 fib(N-2)에 해당하기 때문이다

 

2️⃣시간을 줄여보기 위해 N+1 길이의 배열을 만들고, VIP석은 true로 표시

- 이로써, 1~N 순회 시, 일반석인지 VIP석인지 O(1)에 파악 가능

 

3️⃣연속하는 일반석이면 피보나치 수열을 순회하고, VIP석이면 원점으로 초기화한 뒤 가짓수를 곱셈

 

 

📍코드 (JavaScript)

const [in1, in2, ...in3] = require("fs")
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split("\n");

const solution = () => {
  const N = +in1;
  const M = +in2;
  if (N === M) return 1;

  const answer = [];

  // VIP석 번호의 index를 true로 할당한 배열
  const arrM = Array(N + 1).fill(false);
  in3.map((el) => (arrM[+el] = true));

  // 피보나치 수열 미리 만들어놓기
  const fib = [0, 1, 2];
  for (let i = 3; i <= N - M; i++) {
    fib[i] = fib[i - 2] + fib[i - 1];
  }

  // DP
  let currentIdx = 0;
  let currentVal = 1;
  for (let i = 1; i <= N; i++) {
    // 일반석
    if (!arrM[i]) {
      currentVal = fib[++currentIdx];
      // VIP석
    } else {
      answer.push(currentVal);
      currentIdx = 0;
      currentVal = 1;
    }
  }
  answer.push(currentVal);

  return answer.reduce((acc, cur) => acc * cur, 1);
};

console.log(solution());

 

📍리뷰

- VIP석 정보를 미리 배열에 저장하여 다른 풀이에 비해 확실히 시간복잡도가 좋은 편이었다