[Algorithm] 2302. 극장좌석

2302: 극장좌석(DP)

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

• 문제 티어 : S1
• 풀이 여부 : Failed
• 소요 시간 : 49:42

정답 코드

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())

vips = list(int(input()) for _ in range(M))

dp = [[0]*2 for _ in range(N+1)]

dp[1][0] = 1
dp[1][1] = 0

for vip in vips:
    dp[vip][1] = -1

for i in range(2, N+1):
    if dp[i][1] == -1:
        if dp[i-1][1] != -1:
            dp[i][0] = dp[i-1][0] + dp[i-1][1]
            dp[i][1] = -1
        else:
            dp[i][0] = dp[i - 1][0]
            dp[i][1] = -1
    else:
        if dp[i-1][1] != -1:
            dp[i][0] = dp[i-1][0] + dp[i-1][1]
            dp[i][1] = dp[i-1][0]
        else:
            dp[i][0] = dp[i-1][0]
            dp[i][1] = 0

if dp[N][1] == -1:
    print(dp[N][0])
else:
    print(dp[N][0] + dp[N][1])

접근 방식

https://velog.io/@mimmimmu/BOJ-2302번-극장-좌석-파이썬
다른 풀이들과 gpt를 동원해도 87%에서 인덱스 에러가 발생했었다.
위 블로그를 참고해 코드를 다시 작성했는데, 풀이 방법에서의 차이점은 블로그 필자분은 dp를 2차원 배열로 생성해서 풀이하셨다.

• 기본 경우
  • 안 바꾸는 경우: dp[i-1][0] + dp[i-1][1]
  • 바꾸는 경우: dp[i-1][0] (이전에 이미 바꾸면 X)
• vip 좌석이 앞에 있는 경우
  • 안 바꾸는 경우: dp[i-1][0]
  • 바꾸는 경우: 0

위와 같은 경우로 나눠서 풀이하셨다.
아직 완벽히 이해를 못했다… ^^ 내일 다시 풀어봐야지!

접근 시행착오(+ 코드)

런타임에러의 연속이었고… 어떤 예외상황에서 인덱스에러가 난 것인지 못찾겠다 😂

vip 배열의 각 원소를 기반으로 구간을 잘라, n개의 수로 만들 수 있는 경우의 수만큼을 누적해 곱해주는 방식으로 풀이했다.

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())
vips = [0] + [int(input()) for _ in range(M)] + [N+1]

dp = [1] * (N+1)
dp[2] = 2

for i in range(3, N+1):
  dp[i] = dp[i-2] + dp[i-1] 

ans = 1
for i in range(1, M+2): # vips의 원소를 기준으로 구간을 잘라 dp에서 해당 값을 누적해 곱합
  ans *= dp[vips[i] - vips[i-1] - 1]
print(ans)

배운점 또는 느낀점

대체 어디서 인덱스에러가 났을까!!!!!🥵😂