[BOJ] 2302 - 극장 좌석 (Python)

 

 

아이디어

 

규칙을 찾고 동적 계획법으로 가짓수를 계산한다.

 

 

풀이

 

고정석으로 구분된 연속된 좌석에 대해 그 가짓수가 좌석 개수에 따라 피보나치 수열을 이루고 있다.

리스트 vip에는 0과 좌석 끝 번호를 추가하여 고정석 번호를 저장하고, 리스트 dp에는 피보나치 수열을 저장한다.

전체 가짓수는 연속된 일반 좌석들의 곱이므로 결과값 res에 일반 좌석 개수에 따른 피보나치 수열의 수를 곱한다.

 

import sys

input = sys.stdin.readline

def solution():
    N = int(input())
    M = int(input())
    vip = [0]+[int(input()) for _ in range(M)]+[N+1]
    dp = [1]*(N+1)
    for i in range(2, N+1):
        dp[i] = dp[i-1]+dp[i-2]
    res = 1
    for i in range(1, M+2):
        res *= dp[vip[i]-vip[i-1]-1]
    print(res)

solution()