[백준] 2156번(포도주 시식)

백준 2156번

최종 제출 코드

import sys

input = sys.stdin.readline

N = int(input().rstrip())
array = [0]*N
dp = [0, 0, 0, 0]

for i in range(N):
  array[i] = int(input().rstrip())

for j in range(0, N, 2):
  if j == N-1:
    ele1 = dp[0]
    ele2 = dp[1] + array[j]
    ele3 = dp[2] + array[j]
    ele4 = dp[3] + array[j]
  else:
    ele1 = max(dp[1], dp[3]) + array[j] + array[j+1]
    ele2 = max(dp[1],dp[2],dp[3]) + array[j]
    ele3 = max(dp[0],dp[1],dp[2],dp[3]) + array[j+1]
    ele4 = max(dp[0],dp[1],dp[2],dp[3])
    
  dp[0] = ele1
  dp[1] = ele2
  dp[2] = ele3
  dp[3] = ele4

print(max(dp))

.
◼ 연속해서 마실 수 있는 포도주는 최대 2잔이다.
◼ 원소 2개를 묶어 하나의 경우의 수로 간주한다.

• (1) (O, O) = array[j]+array[j+1], (2) (O, X) = array[j], (3) (X, O) = array[j+1], (4) (X, X) = 0
• 이번 차례에 (1)이 오려면 이전 차례가 (2) OR (4) 였어야 한다.
• 이번 차례에 (2)가 오려면 이전 차례가 (2) OR (3) OR (4) 였어야 한다.
• 이번 차례에 (3)이 오려면 이전 차례가 (1) OR (2) OR (3) OR (4) 였어야 한다.
• 이번 차례에 (4)가 오려면 이전 차례가 (1) OR (2) OR (3) OR (4) 였어야 한다.
• 이전 차례에 올 수 있는 경우의 수 중 최대값을 선택하여 이번 차례의 값을 더한다.

dp[0] = max(dp[1], dp[3]) + array[j] + array[j+1]
dp[1] = max(dp[1],dp[2],dp[3]) + array[j]
dp[2] = max(dp[0],dp[1],dp[2],dp[3]) + array[j+1]
dp[3] = max(dp[0],dp[1],dp[2],dp[3])

◼ 입력값이 홀수개일 경우 고려(j == N-1)

• 이번 차례에 (O)가 오려면 이전 차례가 (2) OR (3) OR (4) 였어야 한다.
• 이번 차례에 (X)가 오려면 이전 차례가 (1) OR (2) OR (3) OR (4) 였어야 한다.
• 최대값을 찾는 것이 목표임으로 (O)가 올 수 있는 경우는 무조건 array[j]를 더한 값으로 dp를 갱신

dp[0] = dp[0]
dp[1] = dp[1] + array[j]
dp[2] = dp[2] + array[j]
dp[3] = dp[3] + array[j]