[BOJ][DP] 2156 포도주 시식

https://www.acmicpc.net/problem/2156

< 문제 >

개인적으로 생각하는데 꽤 시간이 든 문제..

지금 돌아보니 그렇게 오래 걸릴 문제는 아닌 것 같은데..

뭐, 다 그런게지. 

< 풀이 >

이 문제에서의 포인트.

연속으로 놓여있는 3개 이상의 포도주를 마실 수 없다.

DP는 항상 어려운게, 점화식 하나 세우는게 힘들다.

작은 경우에서 큰 경우로 확장을 시키면서 점화식을 만들어야 하는게 DP의 포인트.

~식으로 ~처리가 되어서 결국 마지막에 x 값이 제일 큰 값이 된다. 라는 전개를 해야한다.

포도주의 용량을 담는 배열을 wine. 

각각의 dp값을 담는 dp배열이 있을 때,

N개의 와인이 있으면, 시식하는 3가지의 경우가 발생한다.

1. N번째 와인을 마시고 N-1, N-3 와인을 마신다.

2. N번째 와인을 마시고 N-2 와인을 마신다. 

3. N번째 와인을 마시지 않고, N-1 와인을 마신다. 

위를 바탕으로 점화식을 세우면 

1. wine[i] + wine[i-1] + dp[i-3]

2. wine[i] + dp[i-2]

3. dp[i-1]

우선, 초기값으로 dp[1], dp[2]를 각각 wine[1], wine[1] + wine[2]로 초기화.

3번째 부터는 위의 점화식을 바탕으로 서로 비교하여

최대로 큰 값을 dp[i]에 넣어준다.

dp[i] = MaxVal(wine[i] + wine[i-1] + dp[i-3], wine[i] + dp[i-2], dp[i-1])

< 소스 >

GitHub