[백준/python] 2302 - 극장 좌석

2302번: 극장 좌석

n = int(input())
m = int(input())
lst = [ int(input()) for _ in range(m)]
dp = [0] * 100
dp[0] = 1
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
    dp[i] = dp[i-1] + dp[i-2]

if m > 0 :
    chunck = []
    rst = 0
    for i in lst:
        chunck.append(i - rst - 1)
        rst = i
    chunck.append(n - rst)
    answer = 0
    rst2 = 1
    for i in chunck:
        answer = dp[i] * rst2
        rst2 = answer
else:
    answer = dp[n]
print(answer)

| 알고리즘

• dp는 사람의 수에 따른 자리를 앉는 것의 경우의 수이다. 만약 1명일 경우 경우의 수는 1, 두 명일 때는 2, 세명일 때는 3, 4명일 때는 5개이다. 따라서 dp는 전전 명 수 + 전 명수로 점화식을 세울 수 있다.
• vip수가 0보다 클 때, vip 수에 따른 좌석을 덩어리로 나누어준다.
• 만일 vip 좌석이 [4, 7]이라면 4 - 0  - 1 = 3, 그리고 rst에 4가 들어가서 7 - 4 - 1 = 2, 마지막으로 9 - 7이 되어 2가 되어서 chunk는 [3, 2, 2]로 이루어 진다.
• 그리고 chunk에 맞는 dp, 즉 경우의 수를 찾아서 서로 곱해줌
• 만일 vip 좌석이 0이라면 chunk가 하나이기 때문에 전체 경우의 수는 좌석 수

| 알게된 점

오류 수정

• m이 0일 때, 고려하지 않았음
• n이 1이하일 떼, dp가 리스트가 충분하지 않아서 dp[2]참조 오류
• dp문제 풀 때 dp 리스트의 크기를 충분히 크게 고려하자. 조건 잘보기