[BOJ] 2156. 포도주 시식

Python3,DP

문제

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

입출력

입출력 예시

주요 포인트

경우의 수는 먼저 해당 포도주를 마시는 경우와 안 마시는 경우가 있다.
1. 해당 포도주를 마시는 경우
1) 그 전 포도주를 먹는 경우
2) 그 전 포도주를 먹지 않는 경우
2. 해당 포도주를 안 마시는 경우

출처: https://pacific-ocean.tistory.com/152

w3의 경우의 수를 보면 w1 + w2 는 dp[2]의 값과 같다.
w4의 경우의 수에서는 w2 + w3는 dp[3]이고, w1 + w2 + w4에서 w1 + w2는 dp[2]와 같다.
w1 + w3 + w4에서의 w1은 dp[1]과 같다.

이를 식으로 정리하면,
dp[4 - 1], dp[4 - 2] + w[4], dp[4 - 3] + w[4 - 1] + w[4]

일반화 시키면,
dp[i - 1], dp[i - 2] + w[i], dp[i - 3] + w[i - 1] + w[i]
이다.

최종 코드

n = int(input())
w = [0]
dp = [0]

for i in range(n):
    w.append(int(input()))
    
dp.append(w[1])
if n > 1:
    dp.append(w[1] + w[2])

for i in range(3, n+1):
    dp.append(max(dp[i-1], dp[i-3] + w[i-1] + w[i], dp[i-2] + w[i]))

print(dp[n])

w[1]과 w[2]는 먼저 넣어준다. 이후 3부터 n까지 반복문을 돌린다.

피드백

표로 식을 정리하면 누적합에서 반복되는 것이 보인다.
이를 활용해서 식을 작성하는 게 포인트였다.