코드

import sys

input = sys.stdin.readline

N = int(input())
M = int(input())
VIP = [int(input()) for _ in range(M)]


dp = [0]*(N+1)
if N == 1:
    print(1)
elif N == 2:
    if M > 0:
        print(1)
    else:
        print(2)
else:
    dp[1] = 1
    dp[2] = 2

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

    result = 1

    #print(dp)
    if M>0:

        seats = []
        subseats = []
        for i in range(1,N+1):
            if i in VIP:
                if subseats:
                    seats.append(subseats)
                subseats = []
            else:
                subseats.append(i)
        seats.append(subseats)
        #print(seats)

        for c in seats:
            if len(c) != 0:
                result *= dp[len(c)]

        print(result)
    else:
        print(dp[N])

풀이

• 우선 dp 공식은 dp[i] = dp[i-1] + dp[i-2].
• VIP의 지정된 좌석을 제외한 연속된 리스트를 뽑아내는 방법에서 조금 시간이 걸림.
• VIP 리스트에 i가 없으면 subseats에 반복적으로 넣고, 만약 VIP 리스트에 있다면 그때까지의 subseats을 최종 seats에 저장.
• 마지막 for문을 빠져나오고 나서 마지막 seats도 저장.
• 문제 예시처럼 1~9에서 4,7이 vip이면 [[1,2,3],[5,6],[8,9]] 가 나오도록 하면, 3x2x2를 통해 최종 result 계산.