[백준 2156] 포도주 시식 (python)

2156번: 포도주 시식

---

DP를 이용하자! 3잔 연속 마시면 안된다는 조건이 엄청 까다로웠다.

가능한 경우는 3가지가 나온다.

1. i-1잔을 안마셨을 때: i-2까지의 최대값(dp[i-2])에 juice[i]을 더해준다.
2. i-2잔을 안마시고, i-1잔을 마셨을 때: i-3까지의 최대값(dp[i-3])에 juice[i-1]잔과 juice[i]을 더해준다.
3. i-2잔과 i-1잔을 모두 마셨을 때: i-1까지의 최대값(dp[i-1])이다. 

 

1. 포도 주스들을 juice 배열에 담아준다.
2. dp배열을 만들어 dp[0]=0, dp[1] = 첫번째 잔으로 세팅해준다.
3. N이 1보다 크다면 dp[2]에 첫번째 잔 + 두번째 잔 값을 넣어준다.
4. for문을 돌려서 위에서 설명한 세가지 경우 중 큰 값을 넣어준다.
5. 마지막 dp[N]을 출력해준다.

 

import sys
input = sys.stdin.readline

N = int(input())
juice = [0]
for _ in range(N):
    juice.append(int(input()))

dp = [0, juice[1]]
if N > 1:
    dp.append(juice[1] + juice[2])

for i in range(3, N+1):
    dp.append(max(dp[i-2]+juice[i], dp[i-1], dp[i-3]+juice[i]+juice[i-1]))

print(dp[N])