99클럽 코테 스터디 12일차 TIL + DP

https://www.acmicpc.net/problem/2156

# 2156 포도주 시식

import sys
input = sys.stdin.readline

n = int(input())
wine = [0]
for _ in range(n):
    wine.append(int(input()))

dp = [0] * (n+1)
dp[1] = wine[1] # 1번째는 첫잔 마시는게 최대

if n > 1:
    dp[2] = wine[1] + wine[2] # 2번째는 첫번째 잔 + 두번째 잔 마시는게 최대

# i번째 와인을 마시고 i-2까지 마신 양
# i번째를 마시지 않음 
# i, i-1번째를 마시고 i-3번째 까지 마신 양 
for i in range(3, n+1):
    dp[i] = max(dp[i-2] + wine[i], dp[i-1], dp[i-3]+wine[i-1]+wine[i]) 
    

print(dp[n])

 

• 포도주 잔의 개수가 1이라면 첫번째 잔을 마시는 것이 최대
• 포도주 잔의 개수가 2라면 첫번째, 두번째 잔을 마시는 것이 최대
• wine은 현재 포도주의 양, dp는 i번째까지 마신 포도주의 최대 양을 나타낸다.
• n이 3이상일 때부터 3번 연속 포도주를 마실 수 없는 점을 고려해야 한다.
  • i번째 포도주를 마시고 i-2까지 마신 양 , i번째를 마시지 않는 경우 (i-1까지 마신 양), i번째, i-1번째 포도주를 마시고 i-3 번째 까지 마신 양의 최댓 값으로 갱신해야 한다.