BOJ 2156 포도주 시식

문제

접근 방법

모든 방법을 탐색하기에는 복잡함…

dp를 써야한다는 생각이 든다

이때, 일반적인 dp와 다르게 연속으로 몇개를 마셨는지 또한 기록을 해야 한다. 이를 기록하기 위해 2차원 배열을 dp에 적용해야 한다.

dp[i][j] -> i번째 잔까지 마셨을 때. 최대 마신 포도주 양. 이때, j번 연속으로 마심

점화식은 현재 연속으로 몇번을 마신 건지에 따라 다르게 설정해야 한다. dp[i][1] = dp[i-1][0]+wines[i] dp[i][0] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2]) dp[i][2] = dp[i-1][1] + wines[i]

정답 코드

import sys
input = sys.stdin.readline

n = int(input())

wines = []

for _ in range(n):
  wines.append(int(input()))

dp = [[0]*3 for _ in range(n)]

dp[0][0] = 0
dp[0][1] = wines[0]
dp[0][2] = 0

for i in range(1,n):
  dp[i][1] = dp[i-1][0]+wines[i]
  dp[i][0] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2])
  dp[i][2] = dp[i-1][1] + wines[i]

print(max(dp[-1]))