[2156] 포도주 시식

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

---

동적 계획법으로 해결하는 문제이다. 이 문제의 중요한 점은 연속으로 놓여 있는 3잔을 모두 마실 수 없다는 것이다.

그래서 2잔을 마시고 건너뛰고 마셔야 한다. 위의 예제처럼 입력이 6 10 13 9 8 1 순으로 들어 왔을 때,

DP[] 배열을 만들 때 2잔 단위로 마실 수 있기 때문에 DP[1] = 6, DP[2] = 6 + 10 = 16 이 된다.

이제 3번째 부터 어떻게 점화식을 세울지 고민해야 하는데, 2잔씩 마시고 건너뛸 수 있기 때문에 3가지를 비교하여 그 중

가장 큰 값을 DP[i] 로 정하여야 한다. DP[i]는 i번째 포도주까지 최대로 마실수 있는 포도주의 양으로 정의한다.

① 현재 i와 i-1 번째 포도주를 마실 수 있는 경우 ( arr[i-1] + arr[i] + DP[i-3] ) 

- 왜 DP[i-3] 을 더하냐면, i와 i-1번째 포도주를 마시게 되면 연속으로 두잔을 마시는 것이기 때문에 i-2번째 포도주는 마시면 안되기 때문이다.

② 현재 i번째 포도주만 마시는 경우 ( arr[i] + DP[i-2] )

- 현재 i번째 포도주만 마시게 되면 i-1번째 포도주는 마시면 안되기 때문에 DP[i-2] 를 더한다.

③ 현재 i번째 포도주를 안마시는 경우 

- 이 경우네는 DP[i-1] 와 비교한다.

이 세가지를 비교하여 최대값을 구하면 i번째까지 최대로 마실 수 있는 포도주의 양이 된다.