BOJ - 2302

백준 문제 링크
극장 좌석

❓접근법

1. VIP가 아닌 좌석에서 움직일 수 있는 경우의 수는 아래와 같다.
   좌석이 0개일 때 1가지
   좌석이 1개일 때 1가지
   좌석이 2개일 때 2가지
   좌석이 3개일 때 3가지
   좌석이 4개일 때 5가지
2. 이를 토대로 점화식을 세워 DP에 저장한다.
3. VIP 좌석을 1로, 나머지를 0으로 저장하여
   문제 예시의 경우 [0, 0, 0, 1, 0, 0, 1, 0, 0]로 나타내어서
   1로 구분한 다음 해당하는 길이를 DP에서 찾아 모두 곱해주었다.
   이 경우 DP[3] x DP[2] x DP[2]에 해당한다고 할 수 있다.
4. 마지막으로 곱한 값을 출력하면 끝!

👌🏻코드

N = int(input())
M = int(input())

array = [0] * N

for _ in range(M):
    x = int(input())
    array[x-1] = 1
    
DP = [0] * (N+1)
DP[0] = 1
DP[1] = 1

for i in range(2, N+1):
    DP[i] = DP[i-1] + DP[i-2]
    
idx = 0
answer = 1

for i in range(N):
    if array[i] == 1:
        x = len(array[idx : i])
        answer *= DP[x]
        idx = i+1
        
    if i == N-1:
        x = len(array[idx:])
        answer *= DP[x]
        
print(answer)