[백준 2156번] 포도주 시식

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

2156번: 포도주 시식

---

문제 유형 : DP

 

풀이과정: 조건을 우선 확인해보았다.

1. 포도주 잔을 선택하면 다 마시고 그자리에 놔둔다.

2. 연속으로 3잔을 마실 수는 없다.

dp[i]는 i번째 까지 마신 포도주의 최대 양이다.

i번째 까지 마신 포도주의 최대 양은 3가지 방법중 최대로 구해낼 수 있다.

1. 현재 양 + 전전까지의 최대양 : arr[i] + dp[i-2]

2. 현재 양 + 전의 양 + 전전전까지의 최대양 : arr[i] + arr[i-1] + dp[i-3]

3. 현재 마시지 않고 전까지의 최대양 : dp[i-1]

---

n= int(input())
arr = []
dp = [0]*n
for _ in range(n):
    arr.append(int(input()))

dp[0] = arr[0]
if n >= 2:
    dp[1] = arr[0]+arr[1]
if n >= 3:
    dp[2] = max(arr[0]+arr[1],arr[0]+arr[2],arr[1]+arr[2])
for i in range(3,n):
    dp[i] = max(arr[i] + dp[i-2], arr[i] + arr[i-1]+ dp[i-3], dp[i-1])
print(dp[n-1])