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

🔗 문제 링크

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

✍️ 문제 풀이

해당 문제는 다이나믹 프로그래밍 문제로, 포도주가 1 ~ n잔까지 있을 때 마실 수 있는 포도주의 최대량을 dp 배열에 차례대로 갱신하는 Bottom-Up 방식으로 풀었다.

1) n에 포도주 잔의 개수를 입력 받아 저장하고, 벡터 glasses를 선언해 포도주 양을 차례대로 입력받아 삽입한다.

2) 1차원 배열 dp를 선언하고, dp[1]은 glasses[1], dp[2]는 glasses[1] + [2]로 초기화한다.

• dp[i] : i 번째 잔까지 있을 때 마실 수 있는 포도주의 최대량
• 첫 번째 잔까지 있을 때는 해당 잔 하나만 마실 수 있음.
• 두 번째 잔까지 있을 때는 첫 번째 잔과 두 번째 잔을 모두 마실 수 있음.

3) i가 3 ~ n일 때까지 최대량을 전부 갱신한다.

• 주어진 문제 조건에 의해 3잔을 연속으로 마실 수는 없음.
• 위 조건에 따라 현재 순서에서 선택할 수 있는 선택지가 3가지 존재
  • 1. 현재 순서 잔을 마시지 않기
       : 해당 경우에는 직전 잔까지의 최대량이 현재 잔까지의 최대량이 된다.
  • 2. 현재 순서 잔을 마시고, 직전 잔도 마시기
       : 해당 경우에는 현재 잔과 직전 잔을 마셨기 때문에, (현재 순서 - 2)번째 잔은 마실 수 X
       -> 때문에 (현재 순서 - 3)번째 잔까지의 최대량 + 직전 잔의 양 + 현재 잔의 양이 현재 잔까지의 최대량이 된다.
  • 3. 현재 순서 잔을 마시고, 직전 잔은 안 마시기
       : 해당 경우에는 (현재 순서 - 2)번째 잔까지의 최대량 + 현재 잔의 양이 현재 잔까지의 최대량이 된다.
  • 위 세가지 값 중 가장 큰 값이 현재 순서 잔까지의 최대량이 되는 것이다.
• 위 과정을 점화식으로 나타내면 (i : 현재 순서 인덱스)
  • dp[i] = max(dp[i - 1], dp[i - 3] + glasses[i - 1] + glasses[i], dp[i - 2] + glasses[i])

4) dp[n]에 n잔까지 있을 때 마실 수 있는 포도주의 최대량이 저장되므로, 이를 출력한다.

🖥️ 풀이 코드

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

int n;
int dp[10001];
vector<int> glasses;

int solution() 
{
	dp[1] = glasses[1];
	dp[2] = glasses[1] + glasses[2];

	for (int i = 3; i <= n; i++)
		dp[i] = max({ dp[i - 1], dp[i - 3] + glasses[i - 1] + glasses[i], dp[i - 2] + glasses[i] });

	return dp[n];
}

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

	cin >> n;
	glasses.push_back(0);
	for (int i = 0; i < n; i++)
	{
		int num;
		cin >> num;
		glasses.push_back(num);
	}
	cout << solution();
}