![[동적 계획법 1] [C++] 2156번. 포도주 시식](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FblOQVG%2FbtqUJXt0txA%2Fg6GZtQ5PcwIgrtMfoAGPyK%2Fimg.png)
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
입력
첫째 줄에 포도주 잔의 개수 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'을 처음부터 풀었다면 먼저 풀어봤을 문제이지만 참고하면 좋을 것 같다.
[동적 계획법 1] [C++] 2579번. 계단 오르기
www.acmicpc.net/problem/2579 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점" data-og-host="www.acmicpc.net" data-og-source-url="https://www.acmicpc.net/proble..
codekodo.tistory.com
'✍️ 코테 준비 > Dynamic Programming' 카테고리의 다른 글
| [동적 계획법 1] [C++] 11054번. 가장 긴 바이토닉 부분 수열 (0) | 2021.02.01 |
|---|---|
| [동적 계획법 1] [C++] 11053번. 가장 긴 증가하는 부분 수열 (0) | 2021.01.25 |
| [동적 계획법 1] [C++] 2156번. 포도주 시식 (0) | 2021.01.25 |
| [동적 계획법 1] [C++] 10844번. 쉬운 계단 수 (0) | 2021.01.24 |
| [동적 계획법 1] [C++] 1463번. 1로 만들기 (0) | 2021.01.19 |
| [동적 계획법 1] [C++] 2579번. 계단 오르기 (0) | 2021.01.14 |
