백준 2156 포도주 시식

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

2156번: 포도주 시식효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규www.acmicpc.net

어려웠다.

g[i]는 포도주의 양

dp[i] 는 i를 마지막으로 마셨을 때 최대인 포도주값이다.

맨 처음에 당연히 i-3+i-1과 i-2를 비교하면 된다고 생각했지만,

사실 i-4+i-1이 i-3+i-1보다 클 수 있다.

ex)

질문을 찾아보다가 https://raejoonee.tistory.com/15를 보고 반례를 찾을 수 있었다.

점화식은

dp[i]=max(dp[i-3]+dp[i-1]. dp[i-2],dp[i-4]+dp[i-1])+g[i]가 된다.

마지막에는 마지막잔을 마시는경우, 안마시는 경우(그전의2개) 밖에 없으므로

dp[n],dp[n-1]을 비교해주면 된다.

코드

n=int(input())g=[0]for _ in range(n):    g.append(int(input()))if n==1:
    print(g[1])elif n==2:    print(g[1]+g[2])elif n==3:
    print(max(max(g[1],g[2])+g[3],g[1]+g[2]))else:    dp=g.copy()
    dp[2]+=dp[1]    dp[3]+=max(dp[1],g[2])    for i in range(4,n+1):
        dp[i]=max(dp[i-3]+g[i-1],dp[i-2],dp[i-4]+g[i-1])+g[i]
    print(max(dp[n-1],dp[n]))