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

문제

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

2302번: 극장 좌석

설계

- vip 사이의 구간별 자리수를 cal 함수에 넣는다.

- cal 함수로 구간별 경우의 수를 구한 뒤 answer에 곱한다.

 

파이썬

# 앉을 수 있는 경우의 수를 계산하는 점화식 함수
def cal(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    elif n == 3:
        return 3
    else:
        dp = [0] * (n + 4)
        dp[0], dp[1] = 1, 1
        for i in range(3, n + 4):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[-1]

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

# VIP를 기준으로 나눠진 구역마다 않을 수 있는 경우의 수를 answer에 곱한다.
answer, start = 1, 0
for i in range(M):
    cnt = (arr[i] - (start + 1))
    start = arr[i]
    result = cal(cnt)
    answer *= result

# for문을 마치고 곱하지 못한 나머지 끝 구역을 곱한다.
cnt = N - start
result = cal(cnt)
answer *= result

print(answer)