[백준/BOJ] 백준 11062번 : 카드 게임

www.acmicpc.net/problem/11062

11062번: 카드 게임

고를 수 있는 카드의 범위가 left~right이고, 지금 카드를 뽑는 사람이 human(1:근우, 0:명우)일 때 근우, 명우가 최선의 전략으로 게임을 할때 얻게 되는 근우의 점수를 구하는 함수를 만들었다. 근우가 카드를 뽑을때는 뽑은 카드는 점수로 들어가며, 근우의 점수를 크게 만들어야 되고, 명우가 카드를 뽑을때는 뽑은 카드는 점수로 들어가지 않으며, 근우의 점수를 작게 만들어야 된다.

 

코드

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

int tc;
int n;
vector<int> card;
int cache[1001][1001];

void Pre()
{
	for (int i = 0; i < 1001; i++)
		for (int j = 0; j < 1001; j++)
			cache[i][j] = -1;
}

//고를 수 있는 카드의 범위가 left~right이고, 지금 카드를 뽑는 사람이 human(1:근우, 0:명우)일때
//근우, 명우가 최선의 전략으로 게임을 할때 얻게 되는 근우의 점수
int Solve(int left, int right, int human)
{
	//카드를 모두 골랐을때
	if (left > right)
		return 0;

	int& ret = cache[left][right];

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

	if (human == 1) //근우일때
	{
		//뽑은 카드는 점수로 들어가며, 근우의 점수를 크게 만들어야 된다
		ret = max(card[left] + Solve(left + 1, right, 0), card[right] + Solve(left, right - 1, 0));
	}

	else //명우일때
	{
		//뽑은 카드는 점수로 들어가지 않으며, 근우의 점수를 작게 만들어야 된다
		ret = min(Solve(left + 1, right, 1), Solve(left, right - 1, 1));
	}

	return ret;
}

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

	int input;

	cin >> tc;

	for (int t = 0; t < tc; t++)
	{
		card.clear();
		Pre();

		cin >> n;

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

		cout << Solve(0, card.size() - 1, 1) << "\n";
	}

	return 0;
}