[백준] 2156 포도주 시식 (파이썬 python)

 

 

문제 링크

 

 

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

2156번: 포도주 시식

 

 

 

문제

 

 

 

 

 

문제 풀이

 

 

포도주가 한 개, 두 개 주어졌을 경우는 별다른 계산 필요없이 첫 번째를 선택하는 경우,

첫 번째 + 두 번째를 선택하는 경우가 최대이다.

세 개 주어졌을 경우에는 (1번 + 3번), (2번 + 3번), (1번 + 2번 [두 개 주어졌을 때의 최댓값) 중

최대의 값을 선택하게 된다.

4개부터 n개의 포도주가 주어졌을 때를 보면,

1) n번째 선택 + (n - 1)번째 선택 + (n - 3)까지의 최댓값

2) n번째 선택 + (n - 2)까지의 최댓값

3) (n - 1)까지의 최댓값

이렇게 세 가지의 경우가 주어지며, 이 중 최댓값이 저장된다.

 

n = int(input())
array = [0] * 10000

for i in range(n):
    array[i] = int(input())

dp = [0] * 10000

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

print(max(dp))