[백준] 2302 극장 좌석 JavaScript

혅·2025년 1월 30일

백준, 프로그래머스 -JavaScript-

목록 보기

189/215

문제

어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다. 예를 들어서, 7번 입장권을 가진 사람은 7번 좌석은 물론이고, 6번 좌석이나 8번 좌석에도 앉을 수 있다. 그러나 5번 좌석이나 9번 좌석에는 앉을 수 없다.

그런데 이 극장에는 “VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.

오늘 공연은 입장권이 매진되어 1번 좌석부터 N번 좌석까지 모든 좌석이 다 팔렸다. VIP 회원들의 좌석 번호들이 주어졌을 때, 사람들이 좌석에 앉는 서로 다른 방법의 가짓수를 구하는 프로그램을 작성하시오.

예를 들어서, 그림과 같이 좌석이 9개이고, 4번 좌석과 7번 좌석이 VIP석인 경우에 <123456789>는 물론 가능한 배치이다. 또한 <213465789> 와 <132465798> 도 가능한 배치이다. 그러나 <312456789> 와 <123546789> 는 허용되지 않는 배치 방법이다.

입력

첫째 줄에는 좌석의 개수 N이 입력된다. N은 1 이상 40 이하이다. 둘째 줄에는 고정석의 개수 M이 입력된다. M은 0 이상 N 이하이다. 다음 M 개의 줄에는 고정석의 번호가 작은 수부터 큰 수의 순서로 한 줄에 하나씩 입력된다.

출력

주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 2^31-1)

예제 입력

9
2
4
7

예제 출력

내가 했던 풀이 방법

좌석에서 고정된 좌석을 기준으로 분리한 좌석들의 경우의 수를 곱해주는 식으로 풀이했다. 위 문제 예시로 들면, 4번과 7번 좌석이 고정되어 있으므로 1-3번 좌석 | 5-6번 좌석 | 8-9번 좌석에 앉을 수 있는 경우의 수를 구하고 동시에 일어나야 하므로 곱해준 값을 출력해주었다.

fix에 마지막에 N+1을 넣어 마지막까지 계산될 수 있도록 한다.
start와 answer를 1로 초기화해준다. answer는 마지막 최종 경우의 수를 곱해주어야 하기 때문에 1이고, start는 왼쪽 좌석부터 시작 좌석을 의미한다.
fix에 담긴 값들을 이용해 각각의 경우의 수를 곱해준다. fix[i]는 해당 좌석이 고정되어 있거나 마지막임을 알린다. 해당 좌석에는 VIP가 앉으므로 그 앞 좌석까지 앉을 수 있는 경우를 찾아야 한다. fix[i]-1을 end로 두고 start와 end를 이용하여 length를 구해준다. length가 0보다 클 경우 (같으면 start가 고정 좌석을 향하고 있기 때문에 무시해야 함) length 크기만큼의 dp 배열을 선언해주고, dp[1]과 dp[2]를 각각 1과 2로 채워준다. (dp[1]은 length가 1일 때를 의미하고 이 때는 무조건 (1) 경우 밖에 없으므로 1이다. dp[2]는 length가 2일 때를 의미하고 (1, 2) 또는 (2, 1)이 가능하므로 2로 저장해준다.)
dp[i]는 위 방식으로 반복하면 dp[i-1]+dp[i-2] 점화식을 가지게 된다. 이후 dp 값들을 모두 채워주고 dp[length]를 answer에 곱해준다.
start를 fix[i]의 다음 좌석으로 이동해준 뒤, 3~5번을 반복한다.
answer를 출력한다.

코드

const fs = require('fs');
let [N, M, ...fix] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

N = Number(N);
M = Number(M);
fix = fix.map(Number);
fix.push(N + 1);

let start = 1;
let answer = 1;

for (let i = 0; i < fix.length; i++) {
  let end = fix[i] - 1;
  let length = end - start + 1;

  if (length > 0) {
    let dp = Array.from({ length: length + 1 }, () => 0);
    dp[0] = 1;
    if (length >= 1) dp[1] = 1;
    if (length >= 2) dp[2] = 2;

    for (let j = 3; j <= length; j++) {
      dp[j] = dp[j - 1] + dp[j - 2];
    }

    answer *= dp[length];
  }
  start = fix[i] + 1;
}

console.log(answer);