2156 포도주 시식

문제

풀이

3잔을 연속으로 마실 수 없다는 것이 키포인트이다.
포도주가 1개 있을 때 생각해보자

n=1일 때에는 1번째 잔을 마시면 된다.
(dp[1] => wine[1])

포도주가 2개 있을 때 생각해보자
n=2일 때에는 1번째 잔, 2번째 잔을 마시면 된다.
(dp[2] => wine[1] + wine[2])

포도주가 3개 있을 때 생각해보자
이 때부터 조건을 생각해야 한다.
즉 3잔을 연속해서 마실 수 없다는 것을 고려하면
n=3일 때에는 (1번째 잔, 2번째 잔), (2번째 잔, 3번째 잔), (1번째 잔, 3번째 잔) 이렇게 3가지 경우가 나온다.
(dp[3] => max(wine[1] + wine[2], wine[1] + wine[3], wine[2] + wine[3]))

포도주가 4개 있을 때 생각해보자
n=4일 때에는 (1번째 잔, 2번째 잔, 4번째 잔), (1번째 잔, 3번째 잔, 4번째 잔), (4번째 잔을 마시지 않을 때) 이렇게 3가지 경우가 나온다.
(dp[4] => max(dp[n-1], dp[n-2] + wine[4], dp[n-3] + wine[3] + wine[4]))

이제 점화식을 생각해보자
(dp[n] => max(dp[n-1], dp[n-2] + wine[n], dp[n-3] + wine[n-1] + wine[n]))

구현

문제를 읽었을 때 DP문제 인 것을 파악했고 점화식을 구하려고 하는데 어려움이 있었다. 아직 부족하다는 것을 느꼈다.