[백준] 2156 '포도주 시식' 파이썬(python)

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

2156번: 포도주 시식

n = int(input())
array = [0]*10000
for i in range(n):
    array[i] = int(input())

# dp[i] is max wine
dp = [0] * 10000
dp[0] = array[0]
dp[1] = array[0]+array[1]
dp[2] = max(array[2]+array[0], array[2]+array[1], dp[1])

for i in range(3, n):
    dp[i] = max(array[i]+dp[i-2], array[i]+array[i-1]+dp[i-3], dp[i-1])

print(max(dp))

Point

• dp테이블을 활용한 DP 문제. 
• 세 가지 경우로 나눠야 한다.
• 첫번째 i번째 포도주를 마시고 i-2번째 포도주까지 마신 경우.
• 두번째 i-1번째 포도주를 마시고 i-3번째 포도주까지 마신 경우
• 마지막 i번째를 마시지 않은 경우