[BOJ][python] 2156. 포도주 시식

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

2156번: 포도주 시식

---

💡IDEA

동적계획법을 사용하는 문제이다.

입력받은 wines를 사용하여 dp를 구성하는데, 0번째 값과 1번째 값은 초기화 해준 후 2번째 값부터 어떻게 계산해야 할지 점점 복잡해진다. 2번째 값은 0번째+1번째 or 1번째+2번째 or 0번째+2번째 중 가장 큰 값으로 설정해준다.

3번째 값 부터는 앞에서 2번째까지 계산해둔 dp를 사용하여 계산해나간다. 연속해서 3잔을 마실 수는 없으므로, 2칸 전에 쉴지 or 1칸 전에 쉴지 or 현재 칸에 쉴지 중 가장 큰 값으로 설정한다.

모든 범위에 대해서 dp를 채우면, 마지막 N-1번째 값이 최대로 마실 수 있는 포도주의 양이다.

 

📌CODE

import sys
input = sys.stdin.readline

n = int(input())
wines = [int(input()) for _ in range(n)]

dp = [0]*n
if n == 1:
    print(wines[0])
elif n == 2:
    print(wines[0]+wines[1])
else:
    dp[0] = wines[0]
    dp[1] = wines[0] + wines[1]
    dp[2] = max(wines[0]+wines[2], wines[1]+wines[2], dp[1])
    for i in range(3, n):
        dp[i] = max(wines[i] + wines[i-1] + dp[i-3], wines[i] + dp[i-2], dp[i-1])
    print(dp[-1])