https://www.acmicpc.net/problem/2156
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
현재의 단계 기준으로 선택할 수 있는 것이 세가지가 있다
1. 현재 + 전 = i-3까지의 값 + 그 전의 포도주 + 지금의 포도주
2. 현재 = i-2까지의 값 + 지금의 포도주
3. 현재X = i-1까지의 값
import sys
n = int(sys.stdin.readline())
# 인덱스 편하게 하기 위해 wine에 0 삽입 & dp에 n+1
wine = [0]
dp = [0] * (n+1)
# 포도주 입력
for _ in range(n):
wine.append(int(sys.stdin.readline()))
# 포도주 1잔 최대 = 포도주 1번의 양
dp[1] = wine[1]
# 포도주 2잔 이상부터
if n >= 2:
# 포도주 2잔 최대 = 포도주 1번, 2번의 합
dp[2] = wine[1] + wine[2]
# 포도주 3잔 부터
for i in range(3, n+1):
dp[i] = max(dp[i-3]+wine[i-1]+wine[i], dp[i-2]+wine[i], dp[i-1])
print(dp[n])
