[동적 계획법 1] [C++] 2156번. 포도주 시식

www.acmicpc.net/problem/2156

2156번: 포도주 시식

 

 

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1≤n≤10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

---

해결 방법

포도주를 마실 수 있는 방법은 어떻게 될까?

 

dp를 n번째 잔까지 마실 때 가장 많은 양의 포도주, grape를 n번째 잔의 포도주라고 가정하자.

 

dp[0] = 0

dp[1] = 첫번째 잔만 있을 때 = grape[1]

dp[2] = 첫번째 잔과 두번째 잔이 있을 때 = grape[1] + grape[2]

 

dp[3] = 첫번째 잔과 두번째 잔, 세번째 잔이 있을 때

(dp[3]부터는 3개의 연속된 잔을 선택할 수 없으므로 다른 규칙을 적용해야 한다.)

 

dp[1] + grape[3] (dp[2]는 grape[1] + grape[2] 이므로 dp[2] + grape[3]을 하게 되면 연속된 세 잔이다.)

dp[0] + grape[2] + grape[3]

 

두 가지의 방법이 나올 수 있다. 따라서 둘 중 더 큰 값을 dp에 저장하면 된다.

 

이를 점화식으로 나타내면 다음과 같다.

dp[i] = max(dp[i-2] + grape[i], dp[i-3] + grape[i-1] + grape[i]) (i ≥ 3)

 

하지만...

 

 

계속 "틀렸습니다"가 나오는 것이었다... 점화식은 문제가 없어보이는데... 결국 구글링을 통해서 다른 블로그를 참고했다.

 

마시지 않는 경우도 생각했어야했는데... 이를 생각을 못했다.

 

따라서 최종적인 점화식은

dp[i] = max(max(dp[i-1], dp[i-2] + grape[i]), dp[i-3] + grape[i-1] + grape[i]) (i ≥ 3) 가 된다.

 

최종 코드는

 

---

아래 문제는 이번 문제보다 상당히 유사한 문제이다.

'동적 계획법 1'을 처음부터 풀었다면 먼저 풀어봤을 문제이지만 참고하면 좋을 것 같다.

 

codekodo.tistory.com/30

[동적 계획법 1] [C++] 2579번. 계단 오르기