[백준/DP/ 2156] 포도주 시식

이미지 클릭시, 문제로 이동됩니닷 :)

전체 포도잔의 개수 n을 입력 받은 후 각 포도잔의 양이 들어있는 정수 값을 받아

전체 합이 최대치가 되도록 구하는 문제이다.

Sol

// w : 와인양
[0, 6, 16, 0, 0, 0, 0]

// dp[i]
16 , 0+10+13 , 6+13+23
0 , 6+13+9 , 16+9+28
0 , 16+9+8 , 0+8+33
0 , 0+8+1 , 0+1+9

import sys
input = sys.stdin.readline
n = int(input())
w = [0] + [int(input()) for _ in range(n)]

dp = [0]*(n+1)
dp[1] = w[1]
if n > 1:
    dp[2] = w[1] + w[2]

for i in range(3, n+1):
    dp[i] = max(dp[i-1], dp[i-3]+w[i-1]+w[i], dp[i-2]+w[i])
print(max(dp))

문제를 풀기가 너무 어려워 다른 분들의 풀이를 이해하였다.