포도주 시식
분류 : 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]이 된다.
'알고리즘' 카테고리의 다른 글
m개의 정수 갯수로 합이 n인 수 만들기 (0) | 2016.09.14 |
---|---|
지폐로 낼 수 있는 가짓수 (0) | 2016.09.13 |
동물원 / DP, 점화식 세우기, 상태 점화식 (0) | 2016.05.26 |
붕어빵 판매하기 / DP, 점화식 세우기 (0) | 2016.05.26 |
욕심쟁이 판다 / 다이나믹 프로그래밍, DP, 알고리즘, deque (0) | 2016.05.26 |