[BOJ/Python] 2302 : 극장 좌석

👉 문제 링크

👉 전체 코드

import sys
input = sys.stdin.readline

n = int(input())
m = int(input()) #고정좌석 (vip)
vip = []
for _ in range(m):
    vip.append(int(input()))

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

ans = 1
if m>0: #vip가 있는 경우
    tmp = 0
    for i in vip:
        ans *= dp[i-1-tmp]
        tmp = i
    ans *= dp[n-tmp]
else: #없는 경우
    ans = dp[n]

print(ans)

👉 풀이

vip를 기준으로 양옆의 경우의 수를 따로 구해 곱하면 답이다.
예를 들어, 4번 7번이 vip인 경우, 1,2,3번 좌석의 경우의 수는 3이고, 5,6번, 8,9번 좌석의 경우의 수는 2이므로 3x3x2 =12

이를 공식으로 나타내면
vip-1, vip-vip-1, n-vip 이렇게 구해지는데
이 중, vip-1, vip-vip-1은 새로운 변수를 사용하여 식을 한번만 사용해도 된다.
tmp 변수에 0을 대입하여 vip-1을, 반복문이 돌 때마다 vip의 값을 하나씩 대입하는 방식.
그리고 n-vip는 그대로 대입.

tmp = 0
    for i in vip:
        ans *= dp[i-1-tmp]
        tmp = i
    ans *= dp[n-tmp] #n-vip