백준2156(파이썬) - 포도주 시식

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

2156번: 포도주 시식

• 이 문제는 딱 보고 DP 문제라고 생각했다.
• 보니까 전에 풀었던 계단 오르기와 같은 문제라고 생각해서 같은 방식으로 풀었는데 계속해서 에러가 났다.
• 그 이유는 계단 오르기와는 다르게 마지막 번째 포도주를 굳이 안마셔도 된다는 점이다. 이렇게되면 i-1번째 인덱스의 DP값도 정답이 될 수 있다.

#이문제는 dp...?
import sys
input = sys.stdin.readline

n = int(input())
data = []
for _ in range(n):
    data.append(int(input()))

dp =[0 for _ in range(n)]

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

print(max(dp))