파이썬) 백준 알고리즘 | 2156번 : 포도주 시식

 

n = int(input())
nums = []
dp = [0] * 10001
for i in range(n):
    nums.append(int(input()))
dp[0] = nums[0]
if len(nums) > 1:
    dp[1] = nums[0] + nums[1]
if len(nums) > 2:
    dp[2] = max(nums[0]+nums[2], nums[1] + nums[2], nums[0] + nums[1])
for i in range(3,n):
    dp[i] = max(dp[i-3] + nums[i-1] + nums[i], dp[i-2] + nums[i], dp[i-1])
print(dp[n-1])

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

2156번: 포도주 시식

 

풀이

nums 배열은 입력 순서로 들어가 있는 배열이고, dp 배열은 그 인덱스에서 최대로 마실 수 있는 포도주 값입니다.

i가 3보다 클 때 i번째에서 선택할 수 있는 경우의 수는 dp[i-1], dp[i-3] + nums[i-1] + nums[i], dp[i-2] + nums[i] 가 

있기 때문에 이 값들 중 최대값을 출력하도록 하면 됩니다.