[파이썬] 백준 2302 극장 좌석

비교적 쉽게 풀었고 규칙만 알면 쉽게 풀 수 있다. 이런 문제는 규칙을 파악하는 게 가장 중요한 것 같다.

 

from collections import deque
import sys
 
 
a=int(sys.stdin.readline())
 
vip = int(sys.stdin.readline())
 
k = []
 
for i in range(0,a):
    k.append(0)
 
 
# k[i]가 1이면 vip
 
for i in range(0,vip):
    k[int(sys.stdin.readline())-1] = 1
 
if sum(k) == len(k):
    print(1)
 
 
 
 
else:
    count = 0
 
    answer = []
 
    dp = [0]*10000
 
    dp[0] = 0
    dp[1] = 1
 
    for i in range(2,len(dp)):
        dp[i] = dp[i-1] + dp[i-2]
 
 
 
    for i in range(0,len(k)):
 
        if k[i] == 0:
            count+=1
 
            if i == len(k)-1:
                answer.append(dp[count+1])
 
 
        else:
            answer.append(dp[count+1])
            count = 0
 
 
    ans = 1
 
    for i in answer:
        ans *= i
 
 
 
    print(ans)