[Baekjoon 2302] 극장 좌석

문제

🤍Ⅰ [Baekjoon 2302 - 극장 좌석]

문제 풀이 방법

이동이 불가능한 VIP 좌석을 기준으로 나눠지는 좌석들의 서로 다른 가짓수를 구해야 한다. 좌석의 개수의 규칙은 피보나치 수열의 규칙과 같음을 쉽게 찾을 수 있다. 피보나치 수열의 구현은 Dynamic Programming을 사용하여 구한다.

1. vip 좌석의 번호를 입력받는다.
2. 바꿀 수 있는 좌석들의 개수를 change에 저장한다.
3. change에 배열에 있는 좌석들의 서로 다른 가짓 수를 dp를 활용하여 구하여 answer에 곱한다.
   1. dp 배열에 값이 0이 아니라면, 이미 계산한 값이므로 바로 반환한다.
   2. dp의 값이 0이라면 재귀적으로 호출하여 값을 dp 배열에 저장한 후, 반환한다.

풀이 코드

Python

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())
vip = [0]+[int(input()) for _ in range(M)]+[N+1]
change = [vip[i+1]-vip[i]-1 for i in range(M+1)]
dp = [0] * (N+1)

def get_change(n):
    dp[0] = 1
    dp[1] = 1

    if dp[n] != 0:
        return dp[n]
    dp[n] = get_change(n-1) + get_change(n-2)
    return dp[n]

answer = 1
for c in change:
    answer *= get_change(c)

print(answer)