BOJ #2156 포도주 시식

읽기 전

• 불필요한 코드나 잘못 작성된 내용에 대한 지적은 언제나 환영합니다.
• 개인적으로 배운 점을 정리한 글입니다.

문제 링크

BOJ #2156 포도주 시식

문제 풀이

i번째 잔을 마셨을 경우 얻을 수 있는 최대 총량을 dp 배열에 저장한다고 하자. 포도주를 시식하는 데 흔히 하기쉬운 실수가 i번째 잔을 마시기 전 연속된 세 개의 잔 조건만 의식하여 dp[u - 3] + w[i - 1] + w[i] 혹은 dp[i - 2] + w[i]만을 비교해 dp배열을 입력할 수 있다. 하지만 이 문제는 1칸 혹은 2칸씩 전진할 수 있다는 제약조건이 걸린 계단 문제와는 달리 3칸을 건너 뛰어도 무방하다. 따라서 dp[i - 3] + w[i - 1] + w[i]가 아니라 i - 3번째 잔까지의 dp 배열 중 최대값이어야 한다.

python 코드

import sys
input = sys.stdin.readline

N = int(input())
dp = [0] # 1번 index로 매핑하기 위함
w = [0] # 1번 index로 매핑하기 위함
for _ in range(N):
    w.append(int(input()))
dp.append(w[1]) # 1번째 잔은 무조건 마심
max_v = dp[0] # i-3번째 잔까지의 최대값 초기화
sol = dp[1] # 현재까지의 최대값
for i in range(2, N + 1):
    dp.append(max(max_v + w[i - 1] + w[i], dp[i - 2] + w[i]))
    max_v = max(max_v, dp[i - 2])
    # 3번 부터는 정상적으로 i-3번째 잔까지의 최대값 반영
    sol = max(sol, dp[-1])
print(sol)