BOJ 백준 11062 : 카드 게임

시작하면서

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

BOJ 11062 - 카드 게임

​

문제 이해

이 문제는 단순히 카드만 뽑으면 되는 것처럼 보이지만 중요한 조건이 있다.

• 서로 자신의 점수를 가장 높이기 위해 최선의 전략으로 게임에 임한다.

이 조건 때문에 단순히 좌/우측에서 가장 큰 숫자만 뽑으면 문제를 틀린다. 바로 뽑을 수 있는 카드 말고도 뒤에 나오는 카드까지 생각을 해야하므로, 최선의 전략을 떠올리지 못하면 모든 경우를 다 해보아야 한다.

이 문제는 사실상 최선의 전략을 찾기는 힘드므로, 모든 경우를 다 해보아야하고 그를 위해 동적 프로그래밍 전략을 사용한다.

• dp[i][j] = i~j 번째 카드가 있을 때 얻을 수 있는 최대 점수
• 근우 차례 : 점수가 최대가 되어야 함
  • dp[i][j] = max(leftCard + leftCard를 뽑은 후 다음 게임, rightCard + rightCard를 뽑은 후 다음 게임)
• 명우 차례 : 점수가 최소가 되어야 함
  • 명우의 입장을 거꾸로 생각하면, 근우의 점수가 최소가 되도록 만들어야 하므로 최소 값을 뽑는다고 생각하면 된다.
  • 명우의 점수이므로 카드 값을 더하지는 않고, dp값만 구해준다. ​

해결

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

using namespace std;

int CardGame(const vector<int>& cards, vector<vector<int>>& dp, int leftIndex, int rightIndex, int turnCount)
{
	if (leftIndex > rightIndex)
		return 0;

	if (dp[leftIndex][rightIndex] != 0)
		return dp[leftIndex][rightIndex];

	// 근우 차례
	if (turnCount % 2 == 0)
	{
		return dp[leftIndex][rightIndex] = max(cards[leftIndex] + CardGame(cards, dp, leftIndex + 1, rightIndex, turnCount + 1),
											   cards[rightIndex] + CardGame(cards, dp, leftIndex, rightIndex - 1, turnCount + 1));
	}
	// 명우 차례
	else
	{
		return dp[leftIndex][rightIndex] = min(CardGame(cards, dp, leftIndex + 1, rightIndex, turnCount + 1),
											   CardGame(cards, dp, leftIndex, rightIndex - 1, turnCount + 1));
	}
}

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

	int T;
	cin >> T;

	while (T--)
	{
		int N;
		cin >> N;

		vector<int> cards(N);
		for (int i = 0; i < N; i++)
		{
			cin >> cards[i];
		}

		vector<vector<int>> dp(N);
		for (int i = 0; i < N; i++)
		{
			dp[i].resize(N);
		}

		CardGame(cards, dp, 0, N - 1, 0);

		cout << dp[0][N - 1] << "\n";
	}

	return 0;
}