[백준]2156 포도주시식 #dp

1. 풀이

3번연속은 안된다. 따라서 경우의 수를 다음과 같이 나눈다

​

(1) i번째를 마시고 i-1번째를 마시는경우

-> (i번째) + (i-1번째) + (i-3번째까지 최대)

(2) i번째를 마시고, i-1번째를 마시지 않는 경우

-> (i번째) + (i-2번째까지 최대)

(3) i번쨰를 마시지 않는경우

-> (i-1번째까지 최대)

​

2. 소스코드

N=int(input())
dp=[0 for i in range(N+3)]
preNum=0
for i in range(3,N+3):
    nowNum=int(input())
    # i번째와 i-1번째를 마시는 경우
    a=preNum+nowNum+dp[i-3]
    # i번째를 마시고, i-1번째를 마시지 않는 경우
    b=nowNum+dp[i-2]
    # i번째를 마시지 않는 경우
    c=dp[i-1]

    dp[i]=max(a,b,c)
    preNum=nowNum
print(dp[N+2])