[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 포도주 시식 (2156)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 포도주 시식 (2156)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[DP] - 포도주 시식 (2156)

 

---

 

2156번: 포도주 시식

[ 문제 ]

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

[ 입력 ]

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

[ 출력 ]

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

 

---

[ 코드 ]

#include<iostream>
#include<algorithm>
using namespace std;

// q[n] : n번째 포도주의 양
// dp[n][i] : 포도주를 i번 연속으로 마실때, 마실 수 있는 전체 포도주의 최대값
// dp[n][0] : q[n]번째 포도주를 마시지 않을 때, 마실 수 있는 전체 포도주의 최대값
// dp[n][1] : 포도주를 1번 연속으로 마실 때, 즉 q[n]번째 포도주를 마실 때, 마실 수 있는 포도주의 최대값
// dp[n][2] : 포도주를 2번 연슥오로 마실 때, 즉 q[n], q[n-1]번째 포도주를 마실 때, 마실 수 있는 포도주의 최대값

int dp[10001][4];
int q[10001]; // n개를 담을 수 있어야 함 (공간)

int main() {
	int N; // 포도주 잔의 개수
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> q[i]; // n번째 포도주의 양까지 채우기
	}

	for (int n = 1; n <= N; n++)
	{
		dp[n][0] = max({ dp[n - 1][0],dp[n - 1][1],dp[n - 1][2] });
		// n번째 포도주를 마시지 않으므로, n-1번째는 0번~2번까지 연속으로 마실 수 있음. (이의 최대값)
		dp[n][1] = dp[n - 1][0] + q[n];
		// n번째 포도주를 마시고, 1번만 연속으로 마셔야 하므로, n-1번째는 한번 이상 마실 수 없음
		dp[n][2] = dp[n - 1][1] + q[n];
		// n번째 포도주를 마시고, 2번만 연속으로 마셔야 하므로, n-1번째는 무조건 마셔야 하며, n-2는 마실 수 없음.
	}

	cout << max({ dp[N][0], dp[N][1], dp[N][2] });
	return 0;
}

#include<iostream>
#include<algorithm>
using namespace std;

// q[n] : n번째 포도주의 양
// dp[n] : q[1] ~ q[n]까지 포도주를 마셨을 때, 마실 수 있는 포도주의 최대 양
int dp[10001]; // n개를 담을 수 있어야 함 (공간)
int q[10001]; // n개를 담을 수 있어야 함 (공간)

int main() {
	int N; // 포도주 잔의 개수
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> q[i]; // n번째 포도주의 양까지 채우기
	}

	dp[0] = 0;
	dp[1] = q[1];
	dp[2] = q[1] + q[2]; // 아래 식의 최대값

	for (int n = 3; n <= N; n++) // dp[0], dp[1], dp[2]는 정의해줘야 함
	{
		// 0번 연속해서 마신 포도주 (q[n]을 마시지 않음) : dp[n-1]
		// 1번 연속해서 마신 포도주 (q[n]을 마심, n-1을 마시지 않음) : dp[n-2] + q[n]
		// 2번 연속해서 마신 포도주 (q[n]을 마심, n-1을 마심, n-2는 마시지 않음) : dp[n-3] + q[n-1] + q[n-2]
		dp[n] = max({ dp[n - 1], dp[n - 2] + q[n] , dp[n - 3] + q[n - 1] + q[n] });

	}

	cout << dp[N];
	return 0;
}