[BOJ] 극장 좌석

---

코드

import sys
# from collections import deque
input = sys.stdin.readline

# input
n = int(input())
m = int(input())
vips = []

for _ in range(m):
    vips.append(int(input()))

# solution
ans = 1
d = [1,1,2] + [0]*(n-2)

for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]

temp = 0
for i in range(1, n+1):
    temp += 1
    
    if i in vips:
        ans *= d[temp-1]
        temp = 0
        continue
        
    if i == n:
        ans *= d[temp]

print(ans)

결과

풀이 방법

• DP 점화식을 세우면 해결할 수 있는 문제이다
• D[1] = (1)
• D[2] = (1,2), (2,1)
• D[3] = (1,2,3), (2,1,3), (1,3,2)
• D[4] = (1,2,3,4), (2,1,3,4), (1,3,2,4), (1,2,4,3), (2,1,4,3)
• 피보나치 수열 점화식임을 알 수 있다
• VIP 자리를 뺀 그룹의 가짓수를 각각 구해서 곱하면 답을 구할 수 있다.

---