공부공간

BOJ - 2156 ) 포도주 시식 본문

알고리즘/Dynamic Programming

BOJ - 2156 ) 포도주 시식

개발자가될수있을까? 2019. 12. 15. 21:01


수열에서 연속되지 않은 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 이하인 경우에는 점화식의 범위가 넘어가서 수동으로 처리해주었다.

 



'알고리즘 > Dynamic Programming' 카테고리의 다른 글

BOJ - 1932 ) 정수 삼각형  (0) 2019.12.15
BOJ - 2579 ) 계단오르기  (0) 2019.12.15
BOJ - 11048 ) 이동하기  (0) 2019.12.15
BOJ - 1937 ) 욕심쟁이 판다  (0) 2019.12.12
BOJ- 1463 ) 1로 만들기  (0) 2019.12.11
Comments