[baekjoon] 백준 2302번(파이썬): 극장 좌석

문제

2302번: 극장 좌석

알고리즘

- 점화식을 구하면 쉽게 풀 수 있는 문제이다.

- 좌석이 1개일 때 경우의 수는 1개이고 좌석이 2개일 때 경우의 수는 2개이고 좌석이 3개일 때 경우의 수는 3개이다.

- 점화식: dp[n] = dp[n - 1] + dp[n - 2]

- 각 좌석의 개수에 따라 경우의 수를 구했다면 vip 유무에 따라 경우의 수를 곱해주면 된다.

- 반복문을 통해 vip 사이에 그룹에 들어가는 경우의 수를 확인해서 곱해줘 출력한다.

- vip가 없다면 n좌석의 경우의 수를 출력한다.

코드

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
vip = [int(sys.stdin.readline()) for _ in range(m)]

dp = [0] * (n + 1)
dp[0] = 1
dp[1] = 1 # 1
dp[2] = 2 # 1 2, 2 1
# dp[3] = 3 # 1 2 3, 1 3 2, 2 1 3

# 점화식 : dp[n] = dp[n - 1] + dp[n - 2]
for i in range(3, n + 1):
    dp[i] = dp[i - 1] + dp[i - 2]


answer = 1 # 경우의 수
# vip의 유무에 따라 경우의 수를 도출
if m > 0:
    pre = 0
    # 반복문을 통해 vip 사이에 그룹에 들어가는 경우의 수를 확인
    for j in range(m):
        answer *= dp[vip[j] - 1 - pre]
        pre = vip[j]
    answer *= dp[n - pre]
else:
    answer = dp[n]
print(answer)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법