[백준] 2156번 : 포도주 시식

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

2156번: 포도주 시식

마실수 있는 포도주 양의 최대값을 구하여라.

 

1. 포도주잔을 선택하면 모든 포도주를 마셔야하고, 원래위치에 다시 놓는다.

2. 연속으로 3개 놓여있는 포도주는 마실 수 없다.

 

테스트 케이스 분석

6
6
10
13
9
8
1

dp[1] = 6

dp[2] = 12

dp[3] = max(juice[1]+juice[3], dp[2])

dp[4] = max(dp[1]+juice[3]+juice[4] ,dp[2]+juice[4], dp[3])

점화식 : dp[n] = max(dp[n-3]+juice[n-1]+juice[n], dp[n-2]+juice[n], dp[n-1])

 

연속으로 놓여있는 3개의 포도주를 마실수 없으므로 4번째 포도주를 마실때에는

1. 첫번째까지 마신 포도주의 합 + 3번째 포도주 + 4번째 포도주

2. 두번째까지 마신 포도주의 합 + 4번째 포도주

3. 세번째까지 마신 포도주의 합

 

중에서 최대값을 선택하면 된다.

n = int(input())
item = []
for _ in range(n):
    item.append(int(input()))
if n > 2:
    dp = [0 for _ in range(n+1)]
    dp[0] = item[0]
    dp[1] = item[0]+item[1]
    dp[2] = max(dp[1], item[0]+item[2], item[1] + item[2])

    for i in range(3, n):
        dp[i] = max(dp[i-1], dp[i-2] + item[i], dp[i-3] + item[i] + item[i-1])

    print(dp[n-1])
else :
    if n == 1:
        print(item[0])
    if n == 2:
        print(item[0]+item[1])