[백준] 2156: 포도주 시식

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

Initial

I thought this was a decision-making DP but it is similar logic to the min. number of steps to reach in Leetcode.

We cannot take 3 consecutive drinks at a time so let's try to think of all the case possible

1) we can take this drink as the first drink of sequence and add accumulated volume of drinks 2 steps ago
like oxo (n-2,n-1,n)

2) we can take this drink as the second drink of sequence
like oxoo (n-3, n-2,n-1,n) and add accumulated volume of drinks at 3 steps ago

3) I forgot this case You can actually choose not to drink this time and add accumulated volume of drinks 1 step ago like oox (n-2,n-1,n)

For 1) dp[i] = lst[i] + dp[i-2]
For 2) dp[i] = dp[i-3] + lst[i-1] + lst[i]
For 3) dp[i] = dp[i-1]

We take the bigger value of either 3.

Solution

mine (wrong for n<=3)

My wrong solution. For when n is less than 3, it is wrong cuz it will print 0.

n=int(input())
lst=[int(input()) for _ in range(n)]
for _ in range(3):
    lst.insert(0,0)
dp=[0,0,0] + [0 for _ in range(n)]
for i in range(3,n+3):
    dp[i]=max(dp[i-2]+lst[i], dp[i-3] + lst[i-1] +lst[i],dp[i-1])
print( dp[-1])

correct

https://pgmjun.tistory.com/101

You should fill the dp for n<=3.

But if you do it like

n = int(input())
arr = [[] for _ in range(n+1)]
for i in range(0,n):
    arr[i] = int(input())

dp = [0] * n # i번째 줄까지에서 마실 수 있는 최대 포도주 양
dp[0] = arr[0]
dp[1] = arr[0] + arr[1]
dp[2] = max(dp[1], arr[0]+arr[2], arr[1]+arr[2])
for i in range(3,n):
    dp[i] = max(dp[i-1], dp[i-2]+arr[i], dp[i-3]+arr[i-1]+arr[i])

print(dp[n-1])

You will get a RunTime(TypeError) error.

Correct way to instantiate DP table is

n = int(input())
arr = [[] for _ in range(n)]
for i in range(0,n):
    arr[i] = int(input())

dp = [0] * n # i번째 줄까지에서 마실 수 있는 최대 포도주 양 
dp[0] = arr[0]
if n > 1:
    dp[1] = arr[0] + arr[1]
if n > 2:
    dp[2] = max(dp[1], arr[0]+arr[2], arr[1]+arr[2])
if n > 3:
    for i in range(3,n):
        # xoox의 경우 : dp[i-1]
        # ooxo의 경우 : dp[i-2]+arr[i]
        # oxoo의 경우 : dp[i-3]+arr[i-1]+arr[i]
        dp[i] = max(dp[i-1], dp[i-2]+arr[i],dp[i-3]+arr[i-1]+arr[i])
print(dp[n-1])