📌 [BOJ] 백준 2156 포도주 시식

📖 문제

📖 예제

📖 풀이

import sys
input = sys.stdin.readline

n = int(input())
dp = [0] * 10001

arr = [0]
for _ in range(n):
  arr.append(int(input()))

dp[1] = arr[1]

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

print(dp[n])

다음 점화식을 이용해 문제를 해결할 수 있다.
dp[i] = max(dp[i-1], dp[i-2] + arr[i], dp[i-3] + arr[i-1] + arr[i])
계단 오르기 문제와 다른 점은 마지막 잔을 고르지 않아도 된다는 점이기 때문에 이전의 누적 값을 그대로 가져와도 되는 부분인 dp[i-1] 부분을 추가하여 점화식을 고려하면 된다.