BOJ 2156 포도주 시식

평범한 dp문제이지만, 왜인지 안 풀리다가 나중에 내 오류를 발견한 문제. 처음 생각한 논리 구조는 다음과 같다.

1. 메모이제이션을 할 배열을 만든다. 배열의 구조는 [[0, 0] for _ in range(n+1)] . 이는 [앞 잔을 안 먹고 현재 잔 먹음, 앞 잔을 먹고 현재 잔 먹음]을 의미한다.
2. for 반복문을 돌며 앞 잔을 먹고 현재 잔을 먹는 경우와 앞 잔을 먹지 않고 현재 잔을 먹는 경우 마실 수 있는 포도주 양을 저장한다.
   • 앞 잔을 먹고 현재 잔을 먹는다는 것은 앞앞잔*을 마시지 않았다는 뜻이므로, dp[i-1][0]의 값과 현재 잔의 값을 더한다.
   • 앞 잔을 먹지 않고 현재 잔을 먹는다는 것은 앞앞잔에서 최대로 마신 값인 max(dp[i-2])에 현재 잔의 값을 더해서 구한다.

dp[i][0] = max(dp[i - 2]) + arr[i - 1]
dp[i][1] = dp[i - 1][0] + arr[i - 1]

하지만 위와 같이 하면 다음과 같은 반례가 생긴다.

<입력>
6
1
1
0
0
1
1

<출력 되어야 하는 것>
4
<출력되는 것>
3

이유는 위의 논리구조는 현재 잔을 마실 때 이전 잔 혹은 그 이전 잔 중 하나는 반드시 마신다고 가정하고 있기 때문이다. 따라서 OOXXOO와 같은 경우를 고려하지 못한다.

이 문제는 현재 잔을 먹지 않는 경우도 포함하면 해결할 수 있다. 고친 논리구조는 다음과 같다.

1. 메모이제이션을 할 배열을 만든다. 배열의 구조는 [[0, 0, 0] for _ in range(n+1)] . 이는 [이번 잔 안 먹음, 앞 잔을 안 먹고 현재 잔 먹음, 앞 잔을 먹고 현재 잔 먹음]을 의미한다.
2. for 반복문을 돌며 현재 잔을 안 먹는 경우, 앞 잔을 먹고 현재 잔을 먹는 경우, 앞 잔을 먹지 않고 현재 잔을 먹는 경우 마실 수 있는 포도주 양을 저장한다.
   • 현재 잔을 먹지 않는다는 것은 이전까지 먹은 값 중 최대만 생각하면 되므로 max(dp[i-1])를 저장한다.
   • 앞 잔을 먹지 않고 현재 잔을 먹는 경우는 앞 잔 안 먹음의 값과 현재 잔의 값을 더하면 고려할 수 있다. dp[i-1][0]의 값과 arr[i]의 값을 더한다. (정확히는 arr[i-1]이다)
   • 앞 잔을 먹고 현재 잔을 먹는다는 것은 앞앞잔에서 안 먹었다는 뜻이므로 dp[i-1][1]의 값과 현재 잔의 값을 더한다.

좀 복잡해보이지만, 코드로 정리하면 의외로 단순하다.

import sys

input = sys.stdin.readline
n = int(input())
arr = [int(input()) for _ in range(n)]
dp = [[0, 0, 0] for _ in range(n + 1)]  # [현재 잔 안 먹음, 앞 잔을 안 먹고 현재 잔 먹음, 앞 잔을 먹고 현재 잔 먹음]
dp[1] = [0, arr[0], arr[0]]
for i in range(2, n + 1):
    dp[i][0] = max(dp[i - 1])
    dp[i][1] = dp[i - 1][0] + arr[i - 1]
    dp[i][2] = dp[i - 1][1] + arr[i - 1]

print(max(dp[-1]))