BOJ - 극장 좌석

문제

BOJ — 극장 좌석

접근 방법

각 사람은 자기 자리 또는 바로 옆자리에 앉을 수 있고, VIP 좌석은 고정되어 있다. VIP 좌석을 경계로 일반 좌석을 연속 구간으로 나눈다. VIP를 건너 자리를 교환할 수 없으므로 각 구간의 경우의 수는 독립이며, 전체 경우의 수는 구간별 결과의 곱이다.

연속된 일반 좌석 length개의 배치 수를 ways[length]라고 하자. 마지막 사람이 자기 자리에 앉으면 앞의 length - 1개 좌석을 배치하면 된다. 왼쪽 사람과 교환하면 마지막 두 자리의 배치가 정해지고 앞의 length - 2개 좌석을 배치하면 된다. 두 경우는 겹치지 않으므로 다음 점화식을 얻는다.

ways[length] = ways[length - 1] + ways[length - 2]

초깃값은 ways[0] = 1, ways[1] = 1이다. 빈 구간도 배치 방법이 하나인 것으로 처리해야, VIP 좌석이 연속되거나 양 끝에 있을 때 곱이 0이 되지 않는다.

반복문으로 좌석 수까지 점화식을 계산하고, 각 VIP 앞 구간과 마지막 VIP 뒤 구간의 값을 곱한다. 모든 변수는 명시적으로 선언해 전역 변수에 의존하지 않는다.

코드

const fs = require('fs')
const input = fs.readFileSync(0, 'utf8').trim().split(/\s+/).map(Number)
const n = input[0]
const vipCount = input[1]
const ways = Array(n + 1).fill(1)
for (let length = 2; length <= n; length++) {
  ways[length] = ways[length - 1] + ways[length - 2]
}

let answer = 1
let previousVip = 0
for (let i = 0; i < vipCount; i++) {
  const vip = input[i + 2]
  answer *= ways[vip - previousVip - 1]
  previousVip = vip
}
answer *= ways[n - previousVip]
console.log(answer)

복잡도와 경계 조건

좌석 수가 n, VIP 수가 m이면 시간은 O(n + m), 추가 공간은 O(n + m)이다. 입력 저장 공간과 점화식 배열을 포함한 값이다.

VIP가 없는 경우에는 ways[n]이 답이다. 모든 좌석이 VIP이거나 VIP가 연속된 경우에는 길이 0인 구간을 올바르게 처리해야 한다.