백준 2156 포도주 시식

과정

• DP. 비슷한 문제: 2579 계단 오르기
• 연속으로 3잔을 마시지 않는 조건에서 최대한 많이 마시기
• 현재 위치까지 따져보았을 때 최대값을 DP에 저장하기.
  • i 위치라고 했을 때 가능한 경우는
  • i를 먹고, i-1를 먹고, i-3까지의 최댓값 더하기
  • i를 먹고, i-2까지의 최댓값 더하기
  • i를 안 먹고, i-1까지의 최댓값 더하기
    • 2579 계단 오르기 문제는 마지막 계단을 꼭 밟아야했지만, 이 문제는 마지막 포도주를 꼭 안먹어도 된다.
    • 현재 위치까지의 최댓값이므로 현재 포도주를 먹지 않은 경우의 수도 따져보아야한다.

N = int(input())
lst = [int(input()) for _ in range(N)]
dp = [0 for _ in range(N)]

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

print(max(dp))