BOJ 백준 2156 : 포도주 시식

시작하면서

이번 문제는 다이나믹 프로그래밍(Dynamic Programming) 카테고리 문제이다.

BOJ 2156 - 포도주 시식

​

문제 이해

​ 이 문제에서 포도주 잔의 개수가 10,000개이므로 무작정 모든 경우의 수를 전부 계산하면 시간 초과가 발생한다. 중요한 부분은 연속으로 놓여 있는 3잔을 모두 마실 수는 없다 조건이다. 연속으로 마실 수 있는 경우의 수가 0잔, 1잔, 2잔으로 제한되어있으므로 각 와인을 마시는 경우의 수를 저장하면서 문제를 해결한다.

​

해결

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
   // sync off
   ios::sync_with_stdio(false);
   cin.tie(0);
   cout.tie(0);
   // sync off

   vector<int> amountOfWine;
   vector<vector<int>> dp;
   int n;

   cin >> n;
   amountOfWine.resize(n);
   dp.resize(3);
   dp[0].resize(n, 0);
   dp[1].resize(n, 0);
   dp[2].resize(n, 0);

   for (int i = 0; i < n; i++)
   {
      cin >> amountOfWine[i];
   }

   dp[0][0] = 0;
   dp[1][0] = amountOfWine[0];
   dp[2][0] = amountOfWine[0];

   dp[0][1] = max({ dp[0][0], dp[1][0], dp[2][0] });
   dp[1][1] = amountOfWine[1];
   dp[2][1] = amountOfWine[0] + amountOfWine[1];

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

   cout << max({ dp[0][n - 1], dp[1][n - 1],dp[2][n - 1] });

   return 0;
}