백준 2156(포도주 시식) - 다이나믹 알고리즘

①

풀이 방법

d[i] : i번째까지 최대로 먹을 수 있는 포도주의 양

i=0인 경우 : d[0] = grape[0] 

i=1인 경우 : d[1] = grape[0]+ grape[1]

i=2인 경우 : grape[0]+grape[1](d[1])와 grape[0]+grape[2]와 grape[1]+grape[2] 의 최댓값을 구한다.

.....

i=n인 경우 :

① 마지막 grape[i]을 먹었을 경우 -> grape[i-1]을 먹은 경우와 먹지 않은 경우가 있다

     1) grape[i-1]을 먹은 경우: grape[i] + grape[i-1] + d[n-3]( n-3번째까지 최대로 먹을 수 있는 포도주의 양)

     2) grape[i-1]을 먹은 경우: grape[i] + d[n-2]

② grape[i]를 먹지 않은 경우 : d[n-1]

이 세가지의 최댓값(max) 구하기

( 단, 인덱스에러가 나지 않기 위해서 if n>1와 if n>2로 나누어서 쓴다 )

import sys
n = int(sys.stdin.readline())
grape = [int(sys.stdin.readline().rstrip()) for _ in range(n)]

#i번째까지 최대로 먹을 수 있는 포도주의 양
d=[0]*n
#i=0인 경우
d[0]=grape[0]
#i=1인 경우
if n>1:
    d[1]=grape[0]+grape[1]
#i=2인 경우
if n>2:
    d[2]=max(d[1],grape[0]+grape[2],grape[1]+grape[2])
#i=n인 경우
for i in range(3, n):
    d[i] = max(grape[i] + grape[i - 1] + d[i - 3], d[i - 2] + grape[i], d[i - 1])

print(max(d))