포도주 시식

해당 문제의 조건을 요약하자면 다음과 같다.

연속으로 놓여 있는 포도주 3잔을 모두 마실 수 없다.

처음에 점화식이 바로 떠오르진 않았지만, 우선적으로 dp배열에 대해서 정의를 해보았다.

dp[i]는 i번째 포도주 잔에서 가장 많이 먹은 양을 담은 배열

dp[2]라면 '2번째 포도주 잔에서 가장 많이 먹은 방법을 저장할 수 있도록 해야겠다.'와 같이 내가 설정한 dp배열에 맞게 설계를 하고자 했다.
그래서 아래 3가지의 조건을 세울 수 있었다.

1. 현재 포도주양, 전 포도주양, 처음부터 전전전 포도주까지 먹은 양중에 가장 많이 먹을 수 있는 방법으로 먹은 포도주(dp[전전전])를 먹는 경우, 즉 전전 포도주를 먹지 않는 경우
2. 현재 포도주양, 처음부터 전전전 포도주까지 먹은 양중에 가장 많이 먹을 수 방법으로 먹은 포도주(dp[전전])를 먹는 경우,즉 전 포도주를 안먹는 경우
3. 처음부터 전 포도주까지 먹은 양중에 가장 많이 먹을 수 방법으로 먹은 포도주(dp[전])를 먹는 경우, 즉 현재 포도주를 안먹는 경우

그래서 다음과 같은 점화식이 나오게 되었다.

dp[i] = max(wine[i] + wine[i-1] + dp[i-3], wine[i] + dp[i-2], dp[i-1])

내 코드는 다음과 같다.

import sys

n = int(sys.stdin.readline().strip())
arr = [0]
dp = [0 for _ in range(n + 1)]  # dp[i]는 i번째 포도주 잔에서 최대로 포도주를 먹은 양을 담는 배열
for _ in range(n):
    arr.append(int(sys.stdin.readline().strip()))

dp[1] = arr[1]

if n >= 2:  # 1이상부터 되므로
    dp[2] = arr[1] + arr[2]

for i in range(3, n + 1):
    dp[i] = max(arr[i] + arr[i-1] + dp[i - 3], arr[i] + dp[i - 2], dp[i - 1])
    #  현재 포도주양, 전 포도주양, 처음부터 전전전 포도주까지 먹은 양중에 가장 많이 먹을 수 있는 방법으로 먹은 포도주(dp[전전전])를 먹는 경우, 즉 전전 포도주를 먹지 않는 경우
    #  두번째 경우는 현재 포도주양, 처음부터 전전전 포도주까지 먹은 양중에 가장 많이 먹을 수 방법으로 먹은 포도주(dp[전전])를 먹는 경우,즉 전 포도주를 안먹는 경우
    #  세번째 경우는 처음부터 전 포도주까지 먹은 양중에 가장 많이 먹을 수 방법으로 먹은 포도주(dp[전])를 먹는 경우, 즉 현재 포도주를 안먹는 경우

print(dp[n])