[백준/파이썬] 2156번: 포도주 시식

문제

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

풀이

• 포도주 잔 선택 => 모두 마심 => 마신 후 원위치
• 연속으로 놓여 있는 3잔을 모두 마실 수 없음
• 가장 많은 양을 마실 수 있어야 함

계단 오르기와 굉장히 유사한 문제입니다.

dp[i]는 i번째까지 최대로 마신 포도주의 양입니다.
계단 오르기와 같이 i-2번째까지 마시고 i번째 포도주를 마신 양(dp[i-2] + arr[i]), i-3번째까지 마시고 i-1번째와 i번째 포도주를 마신양(dp[i-3] + arr[i-1] + arr[i])을 고려해야 합니다.
여기서 차이점이 있다면 i번째를 마시지 않는 경우(dp[i-1])까지 고려를 해야 합니다.

코드

import sys
input = sys.stdin.readline

n = int(input())
arr = [int(input()) for _ in range(n)]
dp = [0] * n

if n <= 2:
    print(sum(arr))
else:
    dp[0] = arr[0]
    dp[1] = arr[0] + arr[1]
    dp[2] = max(arr[0] + arr[2], arr[1] + arr[2], dp[1])
    for i in range(3,n):
        dp[i] = max(dp[i-2] + arr[i], dp[i-3] + arr[i-1] + arr[i], dp[i-1])
    print(dp[-1])