[백준 2156] 포도주 시식

1. 문제

www.acmicpc.net/problem/2156

2156번: 포도주 시식

2. 접근 방법

DP입니다.

 

각 날짜(i일)에 마실 수 있는 와인의 양을 P[i]라고 하고

해당하는 날짜까지 마실 수 있는 와인 양의 최댓 값을 D[i]라고 한다면,

 

3일 연속 마시면 안되니 i번째 날은

D[i] = D[i-1]이거나

D[i] = D[i-2] + P[i] 이거나

D[i] = D[i-3] + P[i-1] + P[i-2]가 됩니다.

이 세가지 경우 중 가장 큰 것을 고르면 됩니다.

 

3. 코드

python

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

n = int(input())
d = [0]*(n+2)
p = [0]+[int(input()) for _ in range(n)]+[0]
solve()
print(d[n])

4. 마치며

dfs, bfs에서 벗어나 dp를 푸니 기분이 좋네요 하하하