[C++] 백준 2156번: 포도주 시식

🔗 문제

2156번: 포도주 시식

2156번: 포도주 시식

 

🖍 풀이

완전 탐색으로 풀면 시간 초과가 나와서 동적 계획법으로 풀어야 하는 문제였다. (경험담)

 

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;
}