[백준] 2156 - 포도주 시식

아이데이션

앞에서부터 값이 쭉 누적되면서, 이전 값을 사용할지말지를 결정하는 느낌으로 보아 다이나믹 프로그래밍으로 풀어야 하는
문제라고 생각했다.

현재의 위치에서 선택할 수 있는 경우의 수는 다음과 같다.

1. 현재 위치의 포도주를 먹지 않고, 직전까지의 누적 값을 그대로 가져온다. (연속으로 3번 먹는 경우 일 수도 있으므로!!)

2. 현재 위치의 포도주를 먹고, i - 2번째까지의 누적 값을 그대로 가져온다. (연속 3번이 아닌 것이 보장되므로!!)

3. 현재 위치와 직전 위치의 포도주를 먹고, i - 3번째 까지의 누적 값을 그대로 가져온다. (마찬가지로, 연속 3번이 아닌 것이 보장되므로!!)

이걸 관계로 나타내면,

cache[i] = max(cache[i - 1], cache[i - 2] + board[i], cache[i - 3] + board[i - 1] + board[i])

이렇게 된다!!

 

풀이

n = int(input())
board = [0] + [int(input()) for _ in range(n)]
cache = [0] * (n + 1)
cache[1] = board[1]

if(n > 1):
    cache[2] = board[1] + board[2]

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

print(max(cache))