[BOJ]2302

BOJ 2302- 극장 좌석

• DP를 이용해서 푸는 문제
• 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. 라는 조건이 존재하므로 자료형 오버플로우 걱정 X

문제 풀이

from collections import defaultdict
import math

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

dy_sits = []
sits = []

for sit in range(1, N + 1):
    if sit in fix:
        if sits:
            dy_sits.append(sits)
        sits = []
        continue
    sits.append(sit)

if sits:
    dy_sits.append(sits)

def count_var(dy_sit):
    memo = defaultdict(int) 
    memo[1] = 1 
    memo[2] = 2

    if len(dy_sit) <= 2:
        return memo[len(dy_sit)]

    for i in range(3, len(dy_sit) + 1):
        memo[i] = memo[i - 1] + memo[i - 2]

    return memo[len(dy_sit)]

count = []
for dy_sit in dy_sits:
    count.append(count_var(dy_sit))

print(math.prod(count))

테스트 케이스

N, M, fix = 9, 2, [4, 7]
N, M, fix = 6, 2, [3, 4]