[DP 알고리즘] 포도주 시식 S1

기출 : BOJ #2156

 

D[n][m] : n번째 포도주에 대해 연속으로 m개 선택한 경우 포도주의 양

 

D[n][2] = D[n-1][1] + 포도주[i]

D[n][1] = D[n-1][0] + 포도주[i]

D[n][0] = max(D[n-1])

 

n = int(input())
val = list()
val.append(0)
for _ in range(n):
    val.append(int(input()))

d = [[0, 0, 0] for _ in range(n+2)]

d[1][0] = val[0]
d[1][1] = val[1]
d[1][2] = val[1]

if n>=2:
    d[2][0] = val[1]
    d[2][1] = val[2]
    d[2][2] = val[1] + val[2]

    for i in range(3, n+1):
        d[i][0] = max(d[i-1])
        d[i][1] = d[i-1][0] + val[i]
        d[i][2] = d[i-1][1] + val[i]

print(max(d[n]))