[Python]동적계획법 백준 2156

   문제

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

이전문제들과 비슷하다고 볼수있다.

계단문제에서 마지막 계단은 꼭 밟아야된다는 조건이 빠진 문제라고 볼 수 있겠다.

마지막 와인을 마시지 않았을때와

마지막와인을 마시고 이전와인을 마셧을때

마지막 와인을 마시고 전전와인을 마셧을때로 나눌수 있다.

import sys
n=int(sys.stdin.readline())
wine=[int(sys.stdin.readline()) for _ in range(n)]
result=[0 for _ in range(n)]
 
 
def max_wine(n):
    result[0]=wine[0]
    if n==1:
        return
    result[1]=wine[0]+wine[1]
    if n==2:
        return
    result[2]=max(result[1],wine[2]+result[0],wine[2]+wine[1])
    if n==3:
        return
    for i in range(3,n):
        #마지막와인을 마시지 않았을때
        #마지막와인과 이전와인 마셧을때
        #마지막와인과 전전와인 마셧을때
        result[i]=max(result[i-1],wine[i]+wine[i-1]+result[i-3],wine[i]+result[i-2])
 
 
max_wine(n)
print(result[n-1])