백준/2156번/포도주 시식/실버1

Problem Link: https://www.acmicpc.net/problem/2156

문제 설명

Site: Baekjoon
Number: 2156
Category: Dynamic Programming
Rank: Silver 1

일렬로 놓아져 있는 포도주를 마시는데, 3잔을 연속으로 마실 수 없다.
이 때 마실 수 있는 포도주의 최댓값을 구하는 문제.

포도주의 잔의 갯수는 1~10000개.
포도주의 양은 1000이하 음이 아닌 정수.

DP 배열을 사용해서 풀 수 있는 문제이다.

DP문제의 필수는 초깃값과 점화식이다.

이 문제는 연속된 3잔을 확인하기 위해 3개의 초깃값이 필요하다. 처음은 첫 잔만 마신 경우, 두번째는 첫잔과 두번째잔을 마신 경우, 세번째는 세 잔중 두개를 골라 최댓값이 나오는 잔을 저장한다.

dp[0] = wines[0];
dp[1] = wines[0] + wines[1];
dp[2] = max(max(wines[0] + wines[2], wines[1] + wines[2]), wines[0] + wines[1]);

보통 이런 유형의 DP문제는 배열 인덱스를 늘려가며 해당 와인잔을 마셨을 때를 가정하여 최댓값을 저장한다.

처음에 와인잔을 무조건 마셨을 때를 가정하고 두칸 전의 와인잔을 마셨을때와, 세칸전과 한칸전을 마셨을때를 가정하고 비교하며 진행하였다.

보통 dp 배열의 끝에서 최댓값을 가지는 것과 달리, 이 경우에는 최대 값이 도중에 나올 수 있으므로 ans값을 꾸준히 갱신한다.

이 경우, 와인잔을 마시지 않고 넘어가는 경우를 계산하지 않아 오답이 난다. Wrong Code

#include <iostream>
#include <algorithm>

using namespace std;

int wines[10000];
int dp[10000];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int N, ans = 0;
	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> wines[i];

	dp[0] = wines[0];
	dp[1] = wines[0] + wines[1];
	dp[2] = max(max(wines[0] + wines[2], wines[1] + wines[2]), wines[0] + wines[1]);

	ans = max(max(dp[0], dp[1]), dp[2]);

	for(int i = 3; i < N; i++)
	{
		// 점화식: 두 칸전과 현재, 세 칸전에 이전 잔과 현재 잔을 마셨을 때를 비
		dp[i] = max(dp[i - 2] + wines[i], dp[i - 3] + wines[i - 1] + wines[i]);
		ans = max(ans, dp[i]);
	}


	cout << ans;

	return 0;
}

반례

10   
0   
0   
10   
0   
5   
10   
0   
0   
1   
10   

출력

35

정답

36

와인잔을 마시지 않은 경우를 고려하여 최댓값을 계속 갱신하는 경우까지 고려한다면 정답이 나온다.

Answer Code

#include <iostream>
#include <algorithm>

using namespace std;

int wines[10000];
int dp[10000];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
		cin >> wines[i];

	dp[0] = wines[0];
	dp[1] = wines[0] + wines[1];
	dp[2] = max(max(wines[0] + wines[2], wines[1] + wines[2]), wines[0] + wines[1]);

	for(int i = 3; i < N; i++)
	{
		// 점화식: 두 칸전과 현재, 세 칸전에 이전 잔과 현재 잔을 마셨을 때를 비교하고, 마시지 않을 때의 값과 비교한다.
		dp[i] = max(max(dp[i - 2] + wines[i], dp[i - 3] + wines[i - 1] + wines[i]), dp[i-1]);
	}

	cout << dp[N-1];

	return 0;
}