2156 - 포도주 시식

1) 문제 설명

- 포도주를 마시는데, 최대로 마실 수 있는 양을 구하는 문제

- 단, 조건은 3잔 연속 마실 수 없다. 

- 예를 들어서, 1,2,3 의 포도주가 있으면

   1+2+3 => 불가 (3잔 연속으로 마실 수 없음)

   1+ 3 => 가능 

   2+3 => 가능 

- 위 경우 답은 5이다. 

문제에 나온 케이스를 가지고 분석해보면, 

 

2) 문제 구현 

- dp[0]은 입력받은 값의 0번째가 무조건 들어간다. (dp[0] = input[0])

- 1일 때는 max(input[1] + dp[0]) 

- 2일 때는 고려할게 하나 더 늘어난다. 3번 연속 마시는 경우를 고려해야한다. 

   input[2]+input[1], input[2] + input[0], dp[1]

  2번째와 첫번째 잔을 마시거나

  2번째와 0번째 잔을 마시거나

  2번째를 마시지 않고 그 전만 마시거나

- 3일때는 고려할 사항 한 가지 더 늘어난다. 

   현재 잔을 마시지 않고 , 이전껄로 만족하거나 (d[i-1])

   현재 잔을 마시고, 2번째 전껄로 더한다. (input[i] + dp[i-2])

   현재잔 마시고, 이전잔 마시고, 그 이이전의 합을 취한다.(input[i] + input[i-1] + d[i-3])

 

이렇게 하면 건너뛰면서 마실 수 있다. 

import sys

t = int(input())
lst = []
for _ in range(t):
    lst.append(int(input()))

dp = [0] * (t)

dp[0] = lst[0]

for i in range(1, t):
    if i == 1:
        dp[i] = lst[0] + lst[1]
    elif i == 2:
        dp[i] = max(lst[2] + lst[1], lst[2] + lst[0], dp[1])
    else:
        dp[i] = max(dp[i-1], dp[i-3] + lst[i-1] + lst[i] , dp[i-2] + lst[i])
print(dp[t-1])