백준 2156 파이썬(DP)

다이나믹 프로그래밍 문제는 점화식을 풀어서 해결해야 하는 경우가 많다는 것을 기억하자.

이 문제도 점화식을 사용해보면 해결할 수 있다.

 

i번째 포도주를 시음한다고 하면 생각할 수 있는 경우의 수는

1.  i-2번째 포도주를 마신 경우

2.  i-3번째 i-1번째 포도주를 마신 경우

또한 i번째 포도주를 마시지 았았을 경우 생각할 수 있는 경우의 수는

3.  i-1번째 포도주를 마신 경우이다.

 

이 세가지 경우의 수 에서 가장 큰 값을 출력해내면 된다.

이를 점화식으로 표현해보면

dp[i] = max(dp[i-2]+w[i], dp[i-3]+w[i-1]+w[i], dp[i-1])

 

# 2156번: 포도주 시식
# dp문제는 점화식을 만들어봐야 한다.
# 다시 풀어보기!! 아 실력이 안느냐 왜 ㅠㅠ

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

dp = [0]
dp.append(wine[1])
if n > 1:
    dp.append(wine[1]+wine[2])
    for i in range(3,n+1):
        dp.append(max(dp[i-1],dp[i-2]+wine[i],dp[i-3]+wine[i-1]+wine[i]))

print(dp[n])