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

2156번: 포도주 시식

 

 

역시 DP 문제이다. 

 

처음에 이 문제를 풀때는 2차원 배열을 만들어서

D[n][0] = n번째 잔을 마시지 않는 경우 = max(D[n-1][0], D[n-1][1], D[n-1][2])

D[n][1] = n번째 잔을 마시고 연속된 잔의 수가 1인 경우 = D[n-1][0] + a[n]

D[n][2] = n번째 잔을 마시고 연속된 잔의 수가 2인 경우 = D[n-1][1] + a[n]

 

이렇게 풀었는데, 코드가 너무 복잡해지길래 다른 분들의 풀이를 살짝 참고해서 1차원 배열을 사용해서 푸는 방식으로 전환해봤다.

 

 

문제의 조건에 맞게 포도주를 마시는 모든 경우를 만들기 위해 필요한 상황은 다음 세가지로 좁혀진다. 

 

1. n번째 잔을 마시지 않는 경우

2. n번째 잔을 마시고 n-1번째 잔을 마시지 않는 경우

3. n번째 잔과 n-1번째 잔을 마시고, n-2번째 잔을 마시지 않는 경우 

 

말로 표현하면 조금 와닿지 않을 수도 있지만, 길이가 n인 O와 X의 리스트가 있고 O가 세번 연속 오지 않게 줄을 세우려면 필요한 O, X의 파츠는 

 

X

X O

X O O

 

가 되는 것과 같다.

 

점화식으로 나타내면 다음과 같다. 

 

1. D[n-1]

2. D[n-2] + a[n]

3. D[n-3] + a[n-1] +a[n]

 

이 세가지의 경우의 수에 대해 최대값을 구해주면 된다. 

 

 

그렇게 짜서 제출한 코드는 다음과 같은데, 

 

#include <iostream>

int d[10'001];
int a[10'001];

int dp(int n)
{
	if (n == 0) return 0;
	if (n == 1) return a[1];
	if (n == 2) return a[1] + a[2];
	if (d[n] != 0) return d[n];

	d[n] = dp(n - 1);
	if (d[n] < dp(n - 2) + a[n]) d[n] = dp(n - 2) + a[n];
	if (d[n] < dp(n - 3) + a[n - 1] + a[n]) d[n] = dp(n - 3) + a[n - 1] + a[n];

	return d[n];
}

int main()
{
	int n;
	std::cin >> n;
	for (int i = 1; i <= n; ++i)
		std::cin >> a[i];
	std::cout << dp(n);
}

 

 

결과는 시간초과였다. 

DP가 시간초과가 날리가 없는데... 하고 게시판 질문들을 찾아봤는데 

가능한 포도주의 양이 0을 포함한 양의 정수라서 그렇다고 한다. 

 

그러니까, 이미 계산을 했음을 판별하기 위해 if(d[n]!=0)이라는 조건을 사용하였는데, 포도주의 양이 0인 경우에는 계산을 했음에도 불구하고 계산을 안한 것이라고 판별해 중복해서 계산하게 되기 때문이라고 한다. 

 

이를 보완하기 위해 가능한 방법을 두가지를 생각해봤는데, 

 

1. 초기 배열에 0이 아닌 -1을 집어넣기 

2. 계산의 여부를 기록하는 배열을 따로 만들기 

 

가 있을 것 같았다. 

 

 

2번의 경우 메모리를 살짝 더 쓰겠지만 어차피 bool형이고, 차이가 매우 크지는 않을 것 같아서 2번으로 풀어봤고, 통과했다. 

 

#include <iostream>

int d[10'001];
int a[10'001];
bool check[10'001];

int dp(int n)
{
	if (n == 0) return 0;
	if (n == 1) return a[1];
	if (n == 2) return a[1] + a[2];

	if (check[n] == true || d[n] != 0) return d[n];

	d[n] = dp(n - 1);
	if (d[n] < dp(n - 2) + a[n]) d[n] = dp(n - 2) + a[n];
	if (d[n] < dp(n - 3) + a[n - 1] + a[n]) d[n] = dp(n - 3) + a[n - 1] + a[n];

	check[n] = true;
	return d[n];
}

int main()
{
	check[0] = check[1] = check[2] = true;
	int n;
	std::cin >> n;
	for (int i = 1; i <= n; ++i)
		std::cin >> a[i];
	std::cout << dp(n);
}

 

 

 

+) 실버1 찍었다! 올해 안에 골드 찍는게 목표