알고리즘

포도주 시식 / DP, 점화식 세우기

nocomet 2016. 5. 26. 23:14

포도주 시식


분류  : DP

난이도  : 3 / 5

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



여러가지 형태로 변형되는 문제이다. 연속한 수의 합.. 계단 오르기 .. 등

점화식을 잘 세우는게 관건이다.


D[N]  : N번 잔까지 마셨을때, 가장 최대로 마실 수 있는 수라고 하자.


포도주는 연속해서 3잔을 못마신다. 그렇다면, 몇가지 경우의 수로 분류할 수 있다.


N 번째 잔에서 


1. 안마시는 경우

2. 1번째 연속으로 마시는 경우

3. 2번째 연속으로 마시는 경우


1.   안마시는 경우는 그 전의 N-1에서 최대값이 N 번째 잔에서의 최대값이 될 것이다.

D[N] = D[N-1]


2.   1번째 연속으로 마신다는 것은 그 전의 N-1은 마시지 않았단 소리이다. 

N-2는 마셨든 안마셨는 알 수 없는 상태이다.

D[N] = D[N-2] + A[N]


3.    2번째 연속으로 마신다는 것은 N-1 번째 잔을 마시고, N-2 잔은 반드시 마시지 않았단 소리이다.

N-3은 마셨는지 안마셨는지 알 수 없다.

D[N] = D[N-3] + A[N-1] + A[N]


결국 3개중 최대값이 D[N]이 된다.