[Python] 포도주 시식 - 백준 (DP)

해당 글은 백준 2156번 문제 '포도주 시식'을 다룬다.

문제

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

2156번: 포도주 시식

 

설명

해당 문제는 동적 계획법으로 푸는 문제이다.

마지막 n번째 포도주를 마신다면,

1) n-1번째 포도주를 마신 경우, n-2번째 포도주를 마실 수 없고

2) n-1번째 포도주를 마시지 않은 경우, n-2번째 포도주를 마실 수 있다.

그리고 마지막 n번째 포도주를 마시지 않는다면, 이전의 dp값을 가져오면 된다.

즉 점화식은 최대로 마실 수 있는 포도주의 양이므로 아래와 같이 표현된다.

d[i] = max(d[i-1], d[i-2]+data[i], d[i-3]+data[i-1]+data[i])

그리고 포도주의 잔의 개수인 n은 1 이상 입력 조건으로 주어지므로 if문을 통해 인덱스에러를 방지해주어야 한다.

 

코드

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

d = [0]*n
d[0] = data[0]
if n > 1:
    d[1] = data[0]+data[1]
if n > 2:
    d[2] = max(d[1], data[1]+data[2], data[0]+data[2])

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

print(d[n-1])