[BOJ] 문제 2156 포도주 시식 (dp문제)

 

문제 이해

 

포도주가 1~N개 있을 때, 3개의 포도주를 연속해서 마시지 않는 가운데 가장 많이 마실 수 있는 포도주의 양을 구하는 것.

 

 

문제 풀이

 

n번째의 잔을 마시는 경우의 수와 ( ~~~ + n / ~~~  + n-2 + n)

n번째의 잔을 마시지 않을 때의 경우의 수를 계산해서 ( ~~~~ + n-2 + n-1 )

그 중에서 가장 큰 값을 찾는 식.

 

 

주의사항

 

Top-down 식으로 풀 때, recur 메소드의 if 구문식을 세울 때에는 dp[0]의 값도 0으로 제시해주어야 한다.

그렇기 않을 경우 dp[0] = 에도 arrays.fill 메소드로 인해 -1이 채워져있기 때문에

dp[2], dp[1]을 계산하는 recur(2), recur(1)을 건너뛴 채

dp[0]을 계산하는 recur 함수가 돌아서 에러가 발생한다.

 

 

결과

bottom-up

 

Top-down