[백준 2156번] 포도주 시식 -python

문제 링크

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

2156번: 포도주 시식

 

풀이

- 백준 계단 오르기 문제와 유사 

그러나 계단 오르기 문제는 마지막 계단을 꼭 밟아하지만, 본 문제는 마지막 와인을 반드시 마실 필요 없음 

따라서 dp[i]는 i번째 포도주까지 마실 수 있는 최대의 포도주 양이라고 하면,

i번째 포도주를 마시고 i-2 번째까지 최대로 마신 양 과

i번째를 마시지 않고 i-1번째 포도주까지 마신 최대의 양과 

i번째와 i-1번째 포도주를 마시고 i-3번째가지 최대로 마신 양을 비교하여 

가장 큰 값을 dp[i]에 갱신해야한다. 

n = int(input())

wine = []

for _ in range(n):
  wine.append(int(input()))

# n이 1이거나 2일때, 3이상 일때로 나누어서 풀어야 런타임 에러 발생하지 않음 
if n == 1 :
  print(wine[0])
elif n == 2 :
  print(wine[0]+wine[1])
else :

  dp = [0] * n
  dp[0] = wine[0]
  dp[1] = wine[0] + wine[1]

  dp[2] = max(wine[0]+ wine[2], dp[1], wine[1]+ wine[2])

  for i in range(3,n):
    dp[i] = max(wine[i]+dp[i-2], dp[i-1], wine[i]+wine[i-1]+dp[i-3])

  print(max(dp))