BOJ 2156 포도주 시식

https://www.acmicpc.net/problem/2156
시간 2초, 메모리 128MB
input :

• n (1 <= n <= 10,000)
• 포도주의 양 (0 <= 포도주의 양 <= 1,000)

output :

• 최대로 마실 수 있는 포도주의 양 출력.

조건 :

• 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
• 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

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

경우의 수

dp[3]의 경우의 수 / w1 + w2 == dp[2]

dp[4]의 경우의 수 / w2 + w3 == dp[3], w1 + w2 + w4에서 w1 + w2 == dp[2],
w1 + w3 + w4에서 w1 == dp[1]

그래서 식을 세워보자면,
dp[4]의 경우의 수 : dp[4 - 1], dp[4 - 3] + w[4 - 1] + w[4], dp[4 - 2] + w[4]

4를 i로 바꿨을때

dp[i - 1], dp[i - 3] + w[i - 1] + w[i], dp[i - 2] + w[i] 이 세가지 값중 가장 큰 값을 넣어주면 된다.

기호로 만들어 경우의 수를 나타내자.

점화식 찾으려면 저게 제일 나을 거 같다.

import sys

n = int(sys.stdin.readline())
grape = [0]
dp = [0]

for i in range(n):
    data = int(sys.stdin.readline())
    grape.append(data)

dp.append(grape[1])
if n > 1:
    dp.append(grape[1] + grape[2])

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

print(dp[n])![]

리스트 만들 때.
0번 째는 비우고 만드는게 훨 쉬울듯.
점화식의 경우에도 i - 3 이 존재하는데 이게 잘못 하면 리스트 범위 밖으로 나갈 수 있으니 조심하자.

손으로 꼭 그려 보자.