[Baekjoon] 2156번: 포도주 시식

 

 

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

2156번: 포도주 시식

 

---

 

문제 해결 과정

착안

이전에 풀었던 코딩 문제 중, 유사한 문제가 있는데 동적계획법(dynamic programming)을 통해 문제를 해결할 수 있다는 점은 동일하지만 문제에서 주어지는 규칙이 약간 달라 이 부분에 유의하여 문제를 해결하고자 하였다.

 

문제에서 요구한 규칙을 지키면서 최대한 많은 양의 포도주를 마시는 경우를 생각해보면

 

• 포도주 잔을 연속해서 3 잔을 마실 수 없다.
• 최대한 많은 잔을 마시는 것이 유리하므로, 포도주를 마시지 않고 건너뛰는 간격은 1 칸 또는 2 칸만 가능하다.

 

따라서 $n$개의 포도주 잔이 존재할 때, 마지막 번째의 포도주를 반드시 마신다는 가정 하에 최대한 많은 포도주를 마시는 경우는 아래와 같이 4 가지의 경우로 분류해볼 수 있다.

 

(?)의 경우는 마시는지, 아닌지를 모르는 경우를 의미

• $(n-1)$번째 포도주 잔을 마시는 경우
  • $(n-3)$번째 포도주 잔을 마시는 경우: (1)의 경우
  • $(n-4)$번째 포도주 잔을 마시는 경우: (2)의 경우
• $(n-1)$번째 포도주 잔을 마시지 않는 경우
  • $(n-2)$번째 포도주 잔을 마시는 경우: (3)의 경우
  • $(n-3)$번째 포도주 잔을 마시는 경우: (4)의 경우

 

따라서 $n$ 개의 포도주 잔에 대해 $i$번째 포도주 잔의 양을 $w(i)$라고 하고, 마지막 번째의 잔을 반드시 마시면서 규칙을 어긋나지 않고 가장 많이 마실 때의 포도주의 양을 $f(n)$이라고 하면 아래와 같이 표현 가능하므로

 

$$\therefore f(n) = w(n) + \max(\space w(n-1) + \max(\space f(n-4),\space f(n-3) \space ),\space \max(\space f(n-3),\space f(n-2)\space) \space )$$

 

이다. 이와 같이 $f(n)$의 값을 동적계획법으로 구한다면 문제에서 요구하는 답은 $\max(f(n-1), f(n))$ 과 같다.

* $n$번째 포도주를 마시지 않을 때($=f(n-1)$)가 최대일 수 있기 때문.

 

구현

메모리 절약을 위해, 반복문 루프에서 메모이제이션에 사용할 int 형 변수의 개수는 최대 5 개이므로 5 개의 int 형 요소를 갖는 배열을 선언하여 재활용하는 방식으로 구현하였다.

* dp[0]: $f(n)$의 값을 저장, dp[1]: $f(n-1)$의 값을 저장, ... , dp[4]: $f(n-4)$의 값을 저장.

 

반복문이 종료될 때, dp[1]의 값이 dp[2]로, dp[0]의 값은 dp[1]로 한 칸씩 미뤄지기 때문에 dp[1]과 dp[2]의 값 중에서 큰 값을 출력하도록 하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int Wines[10001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N;
	cin >> N;

	int dp[5] = { 0, };
	for (int i = 1; i <= N; i++)
	{
		cin >> Wines[i];

		if (i < 3)
			dp[0] = dp[1] + Wines[i];
		else
		{
			int cand1 = Wines[i - 1] + (dp[4] > dp[3] ? dp[4] : dp[3]);
			int cand2 = dp[3] > dp[2] ? dp[3] : dp[2];
			dp[0] = Wines[i] + (cand1 > cand2 ? cand1 : cand2);
		}
		
		for (int i = 0; i < 4; i++)
			dp[4 - i] = dp[3 - i];
	}

	cout << (dp[1] > dp[2] ? dp[1] : dp[2]) << "\n";
	return 0;
}

 

실행 결과