2156: 포도주 시식

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

2156번: 포도주 시식

설명

테이블 위에 다양한 포주가 들어있는 포도주 잔이 일렬로 놓여있다. 이를 시식하기 위해서 다음 두 가지 규칙이 있다.

• 포도주 잔을 선택하면 그 잔에 있는 포도주는 모두 마셔야하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
• 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

최대한 많은 양의 포도주를 맛보기 원한다. 따라서 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램 작성. 

예를들어, 6개의 포도주 잔이 있고, 각 잔에는 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어있다. 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다. 

핵심 아이디어

우선, 1부터 n까지의 번호가 붙어있는 n개의 잔이 있다, 그리고 각 잔의 양이 다르다. 최대한 많은 양을 먹을 수 있도록 하자. 가령, 6잔의 포도주 (6, 10, 13, 9, 8, 1) 가 있다고 했을 때, 마지막 포도주를 마실지 말지 결정하는 상황이라고 하자. 만약 내가 9,8을 먹었다면 마지막 잔을 먹을 수 없으며 13과9를 마신경우 마지막 잔인 1을 먹을 수 있다. 이때 가장 많이 먹을 수 있는 상황을 고르면 된다.

즉, 현재 포도주를 마실지 말지 결정 할 때는

• 현재 포도주와 이전 포도주를 마시고 전전 포도주는 먹지 않는다. (wine[i]+wine[i-1]+dp[i-3])
• 현재 포도주와 전전 포도주를 마시고 이전 포도주는 먹지 않는다. (wine[i]+dp[i-2])
• 현재 포도주를 마시지 않는다. (dp[i-1])

이렇게 3가지 경우로 나눠볼 수 있다. 3번 케이스에서 d[i-2] + wine[i-1]로 표기하지 않는 이유는 d[i-1]에 해당 케이스를 포함한 최댓값이 저장되어 있기 때문이다. 그리고 포도주 3잔 이하 경우에는 인덱스 에러 방지를 위해 예외처리를 먼저 해준다.

d[i]는 i번째 포도주까지 최대로 마신 포도주의 양이다. 

1. 전전(i-2)까지의 최대 양 + 현재 양 = (dp[n-2] + wine[i])
2. 전전전(i-3)까지의 최대 양 + 전(i-1)번째 양 + 현재 양 = (dp[i-3] + wine[i-1] + wine[i])
3. 전(i-1)까지의 최대 양 = dp[i-1]

세 가지 경우 더 큰 수를 dp에 저장하는 방식입니다. 

코드 구현

# 포도주 잔 수 입력받기
n = int(input())

# 포도주 각 잔에 들어있는 양 입력받기
wine = [0] * 10001
for i in range(1, n+1):
	wine[i] = int(input())
# dp 테이블 초기화
dp = [0] * 10001
dp[1] = wine[1]
dp[2] = wine[1] + wine[2]
# 3번째부터 3가지 경우 비교해서 최댓값을 dp에 저장한다
for i in range(1, n+1):
	# 현재 잔을 먹지 않을 경우 
    # vs 현재 잔 + 이전 잔 먹기
    # vs 현재 잔 + 전전 잔 먹기
    dp[i] = max(dp[i-1], wine[i] + wine[i-1] + dp[i-3], wine[1] + dp[i-2])
print(max(dp))