BOJ - 2156 ) 포도주 시식

---

수열에서 연속되지 않은 3개 미만의 수를 고르면서 최댓값을 출력하는 문제이다.

 

DP로 풀기위해서 점화식을 세워보니, 조건에서 연속하는 3개의 포도주는 마실수 없다고 제시하였다.

 

따라서

 

1. 현재 포도주를 마시지 않을경우 (DP[n-1])

2. 현재 포도주는 마시고 바로 직전 포도주는 안마신경우 즉 n-2까지는 최대인경우 ( DP[n-2] + num[n] )

3. 현재포도주와 직전포도주까지 마시고 연속해서 3잔은 못마시기때문에 n-3까지는 최대인경우

( DP[n-3] + num[n] + num[n-1] )

 

이 3가지중에 가장 큰 값을 DP[n]으로 선택하여서 업데이트 해주면 된다.

 

N <=3 이하인 경우에는 점화식의 범위가 넘어가서 수동으로 처리해주었다.

 

---

---