[BOJ] 2156 / 포도주 시식 / Python

[BOJ] 2156 / 포도주 시식 / Python

[BOJ] 2156 / 포도주 시식 / Python

www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

풀이

주어진 조건에 대한 규칙을 배열을 이용하여 찾을 수 있는 문제이다.

 

i 번째 포도주 선택에 대한 경우의 수는 다음과 같다.

~ i-3	i-2	i-1	i
~	O	O	X
~	O	X	O
~	X	O	O

위의 세 경우 중 가장 양이 커질 경우를 선택하면 된다.

A = dp[i-1]

B = wine[i] + dp[i-2p]

C = wine[i] + wine[i-2] + dp[i-3]

dp[i] = max(A, B, C)

 

N = int(input())

wine = [0] * N
dp = [0] * N

for i in range(N):
    wine[i] = int(input())

dp[0] = wine[0]

if N > 1:
    dp[1] = wine[0] + wine[1]
if N > 2:
    dp[2] = max(dp[1], wine[2]+dp[0], wine[2]+wine[1])

if N > 3:
    for i in range(2, N):
        a = dp[i-1]
        b = wine[i] + dp[i-2]
        c = wine[i] + wine[i-1] + dp[i-3]
        dp[i] = max(a, b, c)

print(dp[-1])