[BOJ] 2156 - 포도주 시식

 

풀이

DP 문제이다. 입력 데이터를 처음부터 살펴보면서 선택의 최댓값을 찾을 것이다.

문제 조건에서 3번 연속으로 포도 잔을 선택할 수 없기 때문에 다음과 같은 경우를 생각해본다.

1. 현재가 0번 연속, 즉 i-2, i-1번이 선택되었다
2. 현재가 1번 연속, 즉 i-2, i 번이 선택되었다
3. 현재가 2번 연속, 즉 i-1, i 번이 선택되었다

변수 설명

• data : i 번째 입력 값
• dp : i 번째 최댓값

Python3 Code

import sys

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

dp = [0] * (n+2) # i번째 최댓값
dp[1], dp[2] = data[1], data[1] + data[2]

for i in range(3, n+1):
    x = dp[i-1] # 연속 0
    y = dp[i-2] + data[i] # 연속 1
    z = dp[i-3]+ data[i-1] + data[i]# 연속 2
    dp[i] = max(x, y, z)

print(dp[n])