[백준] 11062번 카드 게임

11062번: 카드 게임

근우 입장에서 볼 때

 

근우 차례 : 점수가 더 높은 카드를 갖고 감으로써 점수를 최대로 하는 플레이를 해야 함

 

명우 차례 : 명우 입장에선 자신이 이기기 위해 점수가 더 높은 카드를 갖고 갈 것이므로

근우는 근우의 점수를 최소로 하는 플레이를 해야 함

 

DP[i][j] = i번째부터 j번째 카드가 있을 때 근우가 얻을 수 있는 최대 점수

 

근우 차례일 땐 점수를 최대로 해야 하므로

max(왼쪽 카드 + 왼쪽 카드를 뽑고 플레이한 결과, 오른쪽 카드 + 오른쪽 카드를 뽑고 플레이한 결과)

 

명우 차례일 땐 점수를 최소로 해야 하므로

min(왼쪽 카드를 뽑고 플레이한 결과, 오른쪽 카드를 뽑고 플레이한 결과)

 

DP[i][j]에 이미 값이 저장되어 있으면 또 재귀 호출하며 구할 필요 없이

바로 DP[i][j] 값을 리턴해주면 시간 초과에 걸리지 않는다.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int T, N, arr[1001], dp[1001][1001];

int CardGame(int left, int right, int turn) {
	if (left > right) return 0;
	if (dp[left][right]) return dp[left][right];

	if (turn % 2) // 근우 차례
	   return dp[left][right] = max(arr[left] + CardGame(left + 1, right, turn + 1), arr[right] + CardGame(left, right - 1, turn + 1));
	else // 명우 차례 
	   return dp[left][right] = min(CardGame(left + 1, right, turn + 1), CardGame(left, right - 1, turn + 1));
}

int main() {
	cin >> T;
	for (int t = 0; t < T; t++) {
		cin >> N;
		for (int n = 0; n < N; n++) cin >> arr[n];
		CardGame(0, N - 1, 1);
		cout << dp[0][N - 1] << "\n";
		memset(dp, 0, sizeof(dp));
	}
	return 0;
}