135. 2156(포도주 시식)

import sys
input = sys.stdin.readline
N = int(input())

wine=[int(input()) for _ in range(N)]
wineDp = [0]*(N)

try:
    wineDp[0] = wine[0]
    wineDp[1] = max(wine[0] + wine[1], wine[1])
    wineDp[2] = max(wine[0] + wine[1], wine[0] + wine[2], wine[1] + wine[2])

    for i in range(3, N):  
        wineDp[i] = max(wineDp[i-1],wineDp[i-3] + wine[i-1] + wine[i], wineDp[i-2] + wine[i])
       
    print(max(wineDp))
except:
    sum = 0
    for val in wine:
        sum += val
    print(sum)

문제요약

연속해서 세잔은 마시는것이 불가능하다.

그때 제일 많이 시음할 수 있는 양은 얼마인가?

설명

전전 문제인 계단오르기와 비슷하지만, 계단은 꼭 그 곳을 밟아야 하지만 포도주는 해당 부분을 시음하지 않고 지나갈 수 있다.

그에 대한 예가 이것이다.

2000의 양을 시음하고 굳이 1의 양을 시음하는 것보다 시음하지 않고 넘어가 마지막 2000을 먹는 것이 더 최대로 먹을 수 있다는 뜻이다.

    wineDp[0] = wine[0]
    wineDp[1] = max(wine[0] + wine[1], wine[1])
    wineDp[2] = max(wine[0] + wine[1], wine[0] + wine[2], wine[1] + wine[2])

index 2번 부터는 시음을 하지 않고 넘어가도 되는지에 대한 판단이 필요하다.

따라서 2번을 먹지 않은 경우 wine[0] + wine[1] 가 추가된 것이다.

위 경우에는 2000 | 1001 | 1001 로 시음하지 않는 경우가 가장 크다.

계단오르기 문제와 다른 부분도 이 부분이다.

 

    for i in range(3, N):  
        wineDp[i] = max(wineDp[i-1],wineDp[i-3] + wine[i-1] + wine[i], wineDp[i-2] + wine[i])
       
    print(max(wineDp))

index 3번 이상 부터도 시음을 하지 않는 것이 더 최대값을 가질 수 있다라는 것을 알려줘야한다.

순서대로

max(시음을 하지 않음 | 전전전것의 최대양 + 연속 두번의 양 | 전전 것의 최대양 + 현재의 양) 총 세가지 중의 최대값을 비교한다.

 

index : 3일때 2000 | 1002 | 2001

-> 현재 단계에서는 시음을 하는게 가장 큼

 

index : 4일때 2001 | 3001 | 3000

-> 전 단계에서 시음한것보다 전 단계를 시음하지 않고 현재양과 합한 양이 더 큼

 

index : 5일때 3001 | 4000 | 3001

 

결과는 

[1000, 2000, 2000, 2001, 3001, 4000] 과 같이 나올 것이고

그중 가장 큰 값 4000이 답이 된다.