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

[문제 및 출처]

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

2156번: 포도주 시식

[어떻게 풀까?]

계단 오르기와 굉장히 유사하지만 한가지 다른 점이 있는데, 그건 건너뛰는 것이다. 계단오르기의 경우 마지막 계단을 무조건 올라야 했지만 포도주 시식은 그럴 필요가 없다. 또한 필요에 따라서 3개씩 건너서 마셔도 된다.

대충 그림으로 그리면 이런식으로 될 것이다. 중간에 글자는 NO를 쓴것이다 ^^.

[코드]

n = int(input())
nums = []
dp   = [0 for i in range(n)] 
for i in range(n):
    new = int(input())
    nums.append(new) 

if n > 0:
    dp[0] = nums[0]
if n > 1:
    dp[1] = nums[1] + nums[0]
if n > 2:
    dp[2] = max(nums[0]+nums[1], nums[0]+nums[2], nums[1]+nums[2])

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

print(max(dp))