[Python]2156. 포도주 시식

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

2156번: 포도주 시식

 

---

 

1차원 DP

n = int(input())
WINE = [0]+[int(input()) for _ in range(n)]
 
DP = [0] * (n+1)
DP[1] = WINE[1]
 
if n >= 2:
    DP[2] = WINE[1]+WINE[2] # n 이 2보다 작을 땐 런타임에러 발생(index error)
 
for i in range(3, n+1):
    DP[i] = DP[i-1]
    DP[i] = max(DP[i], DP[i-2]+WINE[i])
    DP[i] = max(DP[i], DP[i-3]+WINE[i]+WINE[i-1])
print(DP[n])

 

 

2차원 DP

n = int(input())
WINE = [0]+[int(input()) for _ in range(n)]
DP = [[0]*3 for _ in range(n+1)]
 
for i in range(1, n+1):
    DP[i][0] = max(DP[i-1][0], DP[i-1][1], DP[i-1][2])
    DP[i][1] = DP[i-1][0]+WINE[i]
    DP[i][2] = DP[i-1][1]+WINE[i]
 
print(max(DP[n]))