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

DP 문제인걸 알고 풀어서 감을 잡기 쉬웠던 것 같습니다.
문제의 조건에서 N이 작은 것과 가짓수가 20억을 넘지 않는다는 조건을 보면 DP를 사용해야겠다고 유추 할 수 있을 것 같습니다.

DP에는 각각 VIP가 없다는 가정하에서 i만큼의 길이에서 나올 수 있는 가짓수를 저장해놓고
VIP을 기준으로 나눠서 각 길이만큼 곱해주면 됩니다.

import sys
input = sys.stdin.readline
dp = [0 for _ in range(41)]
dp[1], dp[2] = 1, 2
for i in range(3, len(dp)):
  dp[i] = dp[i-2] + dp[i-1]

n = int(input())
m = int(input())
arr = [0 for _ in range(n+1)]
for _ in range(m):
  vip = int(input())
  arr[vip] = 1
count = 0
res = 1
for i in range(1, len(arr)):
  if arr[i] == 0:
    count += 1
  if arr[i] != 0:
    if count != 0:
      res = res * dp[count]
      count = 0
if count != 0:
  res = res * dp[count]
print(res)