백준 11062(카드게임)

www.acmicpc.net/problem/11062

11062번: 카드 게임

음 바로 직전에 푼 문제와 거의 동일한 문제이다. 

 

그래도 얘기를 좀 해보면 dp를 어떻게 설정할지가 중요하다.

이것 역시 dp는 이중배열로 했고, dp를 배열하나로 값을 지정할 경우 

 

그리디화 된다고 해야되나 그런 느낌이 든다. 

1개를 뽑았을때의 최댓값 이런식으로 값을 구하려고 하면 그리디스럽다 그냥 기분이 실제로는 잘 모르겠다.

 

그래서 dp[i][j]에서 i, j까지 뽑았을때의 최댓값을 저장한다.

 

그러고 나서 내 턴일때 dp[i][j] = max(dp[i+1][j]+cost[i], dp[i][j-1]+cost[j])를 하면 된다.

상대턴이라면 상대가 최대를 갖게끔 하기위해서 

dp[i][j] = min(dp[i+1][j], dp[i][j-1])을 하면 된다.

 

 

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define MAX 1005

int dp[MAX][MAX];
int num[MAX];
int T, N;

int solve(int l, int r, bool even) {
	int &ret = dp[l][r];
	if (ret != -1)return ret;

	if (l == r) {
		if (even)
			return 0;
		else
			return ret = num[l];
	}

	if (even) {
		ret = min(solve(l + 1, r, !even), solve(l, r - 1, !even));
	}
	else {
		ret = max(solve(l + 1, r, !even)+num[l], solve(l, r - 1, !even)+num[r]);
	}
	return ret;
}

int main() {
	cin >> T;
	while (T--) {
		memset(dp, -1, sizeof(dp));
		cin >> N;
		for (int i = 0; i < N; i++) {
			cin >> num[i];
		}
		cout << solve(0, N - 1, false) << "\n";
	}
}