BOJ : 11062 카드 게임

---

[BOJ 11062(G3)리뷰]

언뜻보면 시뮬레이션 문제처럼 보이기도 하고, 그리디 문제처럼 보이기도 하지만 DP문제이다.

항상 가장 오른쪽,왼쪽에 있는 카드만 가능할 수 있다는 점 때문이다.

만약 [1,2,5,2]라는 카드가 있을 때, 근우가 더 큰 2라는 카드를 가져가게 되면 최종 점수는 3점밖에 얻지 못한다. 그 이유는 명우 역시 최선의 전략으로 플레이하기 때문이다.

그렇기에 첫 턴에서 근우가 1이라는 카드를 가져가야 다음턴에 5라는 카드를 가져갈 수 있고 6이라는 최대 점수를 얻을 수 있다.

이렇게 문제를 이해하고 나서도 코드를 짜는게 굉장히 어려웠다. 이걸 어떻게 짜야할까 고민을 많이 했다.

그래서 머리에 구상한 그대로, 근우가 게임을 플레이하는 함수와 명우가 게임을 플레이하는 함수 두개를 구현했다.
그리고 근우는 현재 턴에서 왼쪽에 있는 카드를 택했을 경우와 오른쪽에 있는 카드를 택했을 경우 중 더 큰 점수를 얻을 수 있는 방법을 택해야 한다.

이는 완전탐색으로 구현할 수 있다. 현재 선택할 수 있는 카드가 s부터 e까지라면 왼쪽에 있는 카드를 선택한다면 다음에는 s+1부터 e까지, 오른쪽에 있는 카드를 선택한다면 s부터 e-1에 있는 카드 중 선택할 수 있다.

그리고 이 때 명우 역시 최선의 플레이를 하므로, 명우가 얻을 수 있는 최선의 점수를 계산할텐데, 현재 구간의 합에서 명우가 얻은 점수를 빼주면 근우가 얻게되는 점수를 계산할 수 있다.

예를들어, 게임을 통해서 얻을 수 있는 총 점수가 20점이라 했을때 명우가 12점을 얻었다면 근우는 나머지 8점을 얻게되는것과 같은 이치이다.

따라서 근우는 현재 선택할 수 있는 카드 중 왼쪽에 있는 카드를 선택하고 나머지 카드를 명우에게 넘겨주는 경우와, 오른쪽에 있는 카드를 선택하고 나머지 카드를 명우에게 넘겨주는 경우 중 큰 값이 근우가 얻을 수 있는 최대값이 된다.

기저조건은 카드가 한장남았을때, 근우와 명우가 선택할 수 있는 조건은 그 카드를 선택하는것 밖에 없으니 그 카드의 값을 리턴해주면 된다.

또, 이 과정에서 수많은 재귀호출이 불리게 된다. 그러므로 dp배열을 통해 계속하여 값을 기록하여 시간복잡도를 줄여야한다.

/*
	21.01.21
	BOJ : 11062 카드 게임 (https://www.acmicpc.net/problem/11062)
	다이나믹 프로그래밍
*/
#include <bits/stdc++.h>
using namespace std;

int g_dp[1001][1001];
int m_dp[1001][1001];
int card[1001];
int subsum[1001];
int tc;
int n;

int g_play(int s, int e);
int m_play(int s, int e);

int getsum(int s, int e) {
	return subsum[e] - subsum[s - 1];
}

int g_play(int s, int e) {
	if (s == e) return card[s];
	if (g_dp[s][e] != -1) return g_dp[s][e];
	int left = card[s] + (getsum(s+1,e) - m_play(s + 1, e));
	int right = card[e] + (getsum(s,e-1) - m_play(s, e-1));

	return g_dp[s][e] = max(left, right);
}

int m_play(int s, int e) {
	if (s == e) return card[s];
	if (m_dp[s][e] != -1) return m_dp[s][e];
	int left = card[s] + (getsum(s+1,e) - g_play(s + 1, e));
	int right = card[e] + (getsum(s,e-1) - g_play(s, e - 1));

	return m_dp[s][e] = max(left, right);
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> tc;
	while (tc--) {
		memset(g_dp, 0xff, sizeof(g_dp));
		memset(m_dp, 0xff, sizeof(m_dp));
		cin >> n;
		for (int i = 1; i <= n; i++) {
			cin >> card[i];
			subsum[i] = subsum[i - 1] + card[i];
		}

		cout << g_play(1, n)<<'\n';
	}

	return 0;
}