🔗 문제
2156번: 포도주 시식
효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규
www.acmicpc.net
🖍 풀이
완전 탐색으로 풀면 시간 초과가 나와서 동적 계획법으로 풀어야 하는 문제였다. (경험담)
i번째 잔에는 선택권이 2개가 있다.
- 마시거나
- 마시지 않거나
통합
DP[i] = std::max(
std::max(DP[i-2], DP[i-3] + W[i-1]) + W[i], // i번째 마신 경우
DP[i-1] // i번째 안 마신 경우
);💾 소스
#include <iostream>
#include <algorithm>
const int MAX = 10010;
int main()
{
int N;
int W[MAX] = {0, };
int D[MAX] = {0, };
std::cin >> N;
for(int i=0; i<N; ++i)
std::cin >> W[i];
D[0] = W[0]; D[1] = W[0] + W[1];
for(int i=2; i<=N; ++i)
{
D[i] = std::max(D[i-1], (W[i] + std::max(W[i-1] + D[i-3], D[i-2])));
}
std::cout << D[N];
return 0;
}