[백준/python] 2156 - 포도주 시식

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

 

사용 알고리즘: DP

 

 

n 개의 포도주를 처음부터 차례로 돌면서 먹을지 안 먹을지 결정

 

- i 번째 포도주를 먹지 않는다 -> dp[i-1]

- i 번째 포도주를 먹는다

• i-1 번째 포도주를 먹는 경우 (직전 포도주를 먹는 경우) -> dp[i] = dp[i-3] + wine[i-1] + wine[i]
• i-2 번째 포도주를 먹는 경우 (전전 포도주를 먹는 경우) -> dp[i] = dp[i-2] + wine[i]

 

 

 

점화식: dp[i] = max(진전 포도주를 먹는 경우, 안먹는 경우, 전전 포도주를 먹는 경우) (i > 2)

 

-> dp[i] = max(dp[i-3] + wine[i-1] + wine[i], dp[i-1], dp[i-2] + wine[i])

 

 

 import sys

n = int(sys.stdin.readline())

wine = [0] * 10001 # 인덱스 1 부터 사용
for i in range(1, n+1):
    wine[i] = int(sys.stdin.readline())

# i 번째 잔에 도달 했을 때 먹을 수 있는 포도주의 최대량
dp = [0] * (n+1)

# 초기화
dp[1] = wine[1]

if n >= 2:
    dp[2] = wine[1] + wine[2]

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])