Algo_Spot) NUMBERGAME

문제 : https://algospot.com/judge/problem/read/NUMBERGAME

두 사람이 서로 번갈아가면서 왼쪽 오른쪽 둘중에서 한 카드를 고르거나 게임판에 두개이상의 숫자가 있을경우 왼쪽 오른쪽 둘중에서 2개의 카드를 지우면서 게임을하는데 서로 최선을 다했을경우 나오는 결과를 출력하는 게임입니다.

가지고있는 카드중 맨 왼쪽을 begin 맨 오른쪽을 end로하고 dp를  begin과 end로 찾을수있게 배열을 이차원배열로 생성해습니다.

#include 
#include 
#include 

using namespace std;

#define IMPOSSIBLE -99999

int arr[50];
int cache[50][50];
int n;

int NumberGame(int begin, int end) {
	if (begin > end) return 0;

	int& ret = cache[begin][end];

	if (ret != IMPOSSIBLE) return ret;

	ret = max(arr[begin] - NumberGame(begin + 1, end), arr[end] - NumberGame(begin, end - 1));

	if (begin != end) {
		ret = max(ret, -NumberGame(begin + 2, end));
		ret = max(ret, -NumberGame(begin, end - 2));
	}

	return ret;
}

int main() {
	std:ios::sync_with_stdio(false);
	int C;
	cin >> C;

	while (C--) { // 케이스 시작
		cin >> n;

		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				cache[i][j] = IMPOSSIBLE;
			}
		}

		memset(arr, -1, sizeof(arr));
		
		for (int i = 0; i < n; ++i) {
			cin >> arr[i];
		}

		cout << NumberGame(0, n - 1) << endl;
	}

	return 0;
}