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

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

2156번: 포도주 시식

직전에 연속으로 cnt잔 마셨을 때, index포도주부터 마실수 있는 포도주의 최대 양을 구한다. 직전에 연속으로 2잔을 마신 경우 index포도주는 건너뛰어야 하고, 직전에 연속으로 2잔을 마시지 않았다면 index번 포도주를 마시는 경우와 마시지 않는 경우중 더 큰 양을 선택한다

 

코드

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

int n;
vector<int> drink;
int cache[10000][3];

void makeCache()
{
	//-1로 초기화한다
	for (int i = 0; i < 10000; i++)
		for (int j = 0; j < 3; j++)
			cache[i][j] = -1;
}

//직전에 연속으로 cnt잔 마셨을때, index포도주 부터 마실수 있는 포도주의 최대 양
int solve(int index, int cnt)
{
	//마지막 포도주일때
	if (index == n - 1)
	{
		//직전에 연속으로 두잔 마셨다면
		if (cnt == 2)
			return 0;
		
		else
			return drink[n - 1];
	}

	int& ret = cache[index][cnt];

	//계산한적이 있을때
	if (ret != -1)
		return ret;

	//직전에 2잔을 연속으로 마셨을때 index번 포도주는 마시지 않는다
	if (cnt == 2)
		ret = solve(index + 1, 0);

	//index번 포도주를 마시는 경우와 마시지 않는 경우중 더 큰 양을 선택한다
	else
		ret = max(drink[index] + solve(index + 1, cnt + 1), solve(index + 1, 0));

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int temp;

	//cache 초기화
	makeCache();

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		drink.push_back(temp);
	}

	cout << solve(0, 0);

	return 0;
}