[백준 2156번]포도주 시식

https://www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램입니다.

연속으로 3잔은 선택할 수 없다는 조건이 있는데요.

이 조건을 적용해서 3잔을 마시는 경우에 대해서 생각해봅니다.

1  2  3

X O O

O X O 

O O X 

가 됩니다.

 

이를 확장해서 생각해보면..

앞에서부터 그 항 까지의 합의 최대값을 dp라 할때

~dp + O + O  - (1) 

~dp + X + O  - (2)

~~~~dp + X  - (3)

가 됩니다.

 

여기서

(1)은 마지막 두개가 둘다 선택되는 경우

(2)는 마지막 한개만 선택이 되는 경우

(3)은 마지막을 선택하지 않는 경우

로 나누어 생각할 수 있습니다.

 

(1)인 경우 dp의 마지막 항은 결국 X가 될 것이고 따라서 그보다 하나 더 전까지 항의 최대값이라 생각해도 되겠습니다.

사실상 ~dp-1 + X + O + O  - (1) 가 되는 것이지요.

예시) XOOXOO / OXOXOO / OOXXOO 에서 빨간색 X의 왼쪽항들에 대한 합이 가장 큰 것이 최대값이 됩니다.

 

(2)인 경우 마지막항과 마지막에서 뒤에서 2번째까지의 항들의 최대값의 합을 더하면 되겠습니다.

(3)인 경우 처음부터 뒤에서 두번째항까지의 최대값을 구하면 되겠습니다.

 

 

이렇게 구한 3가지 케이스들로부터 가장 큰 값을 dp에 저장을 해서 구해나가면 됩니다.

 

<소스코드>

# 2156_Drink_Wine.py

import sys

 

n = int(sys.stdin.readline)

 

dp = [0]*(n+3)

v = [0]*(n+3)

 

for i in range(n):

    v[i+1] = int(sys.stdin.readline)

 

dp[1] = v[1]

dp[2] = dp[1]+v[2]

 

for i in range(3,n+1): 

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

    # dp[i] = dp[i-3] + v[i-1] + v[i]   # 마지막에 둘 다 마시는 경우

    # dp[i] = max(dp[i], dp[i-2] + v[i])# 마지막에 한번만 마시는 경우

    # dp[i] = max(dp[i], dp[i-1])         # 마지막에 안마시는 경우...  중 가장 큰값을 dp[i]에 저장

print(dp[n])

 

직관적으로 알아보기 쉽도록 0번째 항은 사용하지 않고 1번째 항부터 값을 저장했습니다.

dp와 v의 크기가 n+3개인 이유는 n이 1,2인 경우 v[1], v[2], dp[1], dp[2]를 저장하는 과정에서 indexError가 발생하기 때문입니다.