[백준 2156] - 포도주 시식(Silver I)

📜문제

👍풀이

import sys

N = int(sys.stdin.readline().rstrip())
arr = [0]
dp = [0 for _ in range(N+1)]

for _ in range(N):
    arr.append(int(sys.stdin.readline().rstrip()))


for i in range(1, N+1):
    if i == 1:
        dp[i] = arr[i]
    elif i == 2:
        dp[i] = dp[i-1] + arr[i]
    else:
        dp[i] = max(dp[i-3]+arr[i-1]+arr[i], dp[i-2]+arr[i], dp[i-1])

print(dp[N])

늘상 보던 dp문제랑 결은 거의 비슷한 문제인데도 결국 못 풀었다.... 사실 비슷하게는 생각했는데 점화식을 세우는데는 실패했다. 참고한 풀이

위와 같은 데이터가 있다고 가정할 때, d[i]를 구하기 위해선 3가지의 케이스를 비교해야 한다.

1. i-3번째까지 포도주를 최대한 마신 후, i-2번째 포도주를 건너뛰고 i-1번째, i번째 포도주를 마시는 경우
2. i-2번째까지 포도주를 최대한 마신 후, i-1번째 포도주를 건너뛰고 i번째 포도주를 마시는 경우
3. i-1번째까지 포도주를 최대한 마신 후, i번째 포도주를 안 마시는 경우
   (i번째 포도주를 안 마심으로써 추후 다른 큰 포도주를 연속으로 마실 수 있는 경우가 있을 수 있으므로 이것까지 고려해주어야 함)

따라서 점화식을 세우면 다음과 같이 세울 수 있고, 문제를 해결할 수 있다.

dp[i] = max(dp[i-3]+arr[i-1]+arr[i], dp[i-2]+arr[i], dp[i-1])