[백준][DP] 2156. 포도주 시식

2156. 포도주 시식

2156번: 포도주 시식

 

• 풀이
  • 3잔 이상 연속으로 마실 수 없다!! << 핵심 포인트
    • 앞의 선택 때문에 현재가 무엇이 최선인지 비교해서 확인을 해봐야 알 수 있음
    • → 그리디가 아니라 DP인 것을 알 수 있음
  • 현재 잔을 추가할때
    • i번째 잔을 안마신다면?
      • i-1, i-2 번째 잔을 다 마셔도 됨 dp[i-1]
    • i번째 잔을 아마신다면?
      • i-1번째 잔을 마신다면 i-2번째 잔을 마실 수 없음 → dp[i-3]+A[i-1]+A[i]
      • i-1번째 잔을 마시지 않는다면? → dp[i-2]+A[i]

n = int(input())
grapes = [0]+[int(input()) for _ in range(n)]
if n < 3:
    print(sum(grapes))
    exit()
dp = [0 for _ in range(n+1)]
dp[1] = grapes[1]
dp[2] = sum(grapes[1:3])
for i in range(3, n+1):
    dp[i] = max(dp[i-2]+grapes[i], dp[i-3]+grapes[i-1]+grapes[i], dp[i-1])

print(dp[n])