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

https://www.acmicpc.net/problem/2302

 

# 최종 정답을 저장할 변수
ans = 1  

# 전체 좌석 개수 N 입력
N = int(input())  

# VIP 좌석 개수 M 입력
M = int(input())  

# DP 배열 선언 (각 크기에 대해 가능한 좌석 배치 경우의 수 저장)
dp = [0 for _ in range(101)]  

# 기본적인 피보나치 초기값 설정 (1개 좌석일 때 1가지, 2개 좌석일 때 2가지 경우)
dp[0] = 1  # 빈 좌석 (계산 편의상 1로 설정)
dp[1] = 1  # [O] → 한 가지 방법
dp[2] = 2  # [OO], [XX] → 두 가지 방법

# DP를 이용해 n개의 좌석을 배치할 수 있는 경우의 수 계산
# 피보나치 수열을 따름: dp[i] = dp[i-1] + dp[i-2]
for i in range(3, 100):  
    dp[i] = dp[i - 1] + dp[i - 2]  

# 현재 처리 중인 일반 좌석의 시작 위치
curr = 1  

# VIP 좌석을 기준으로 나뉘는 구간을 계산
for _ in range(M):
    VIP = int(input())  # VIP 좌석 위치 입력
    ans *= dp[VIP - curr]  # 일반 좌석 구간의 배치 경우의 수를 곱함
    curr = VIP + 1  # 다음 구간의 시작 위치 갱신

# 마지막 VIP 이후 남은 일반 좌석 구간 처리
if curr != (N + 1):
    ans *= dp[N + 1 - curr]  

# 최종 가능한 좌석 배치 방법 수 출력
print(ans)

꽤 많이 헤맸다.. DP 더 파야겠다.. ㅠㅠ