[백준] 11062 - 카드 게임

https://www.acmicpc.net/problem/11062

11062번: 카드 게임

 

약간 까다로운 dp 문제였다. dp 배열의 정의는 제대로 했는데, dp를 적용시키는 과정에서 약간 어려웠다.

 

dp[i][j] = i번째 카드부터 j번째 카드까지 남아있을 때, 얻을 수 있는 최대 점수

로 정의해서, dp[1][n]을 top-down 방식으로 구하면 된다.

 

게임 이론 문제 같은 경우에는 양 측이 항상 최선의 방식대로 진행한다.

그래서 양 측 턴이 번갈아 가면서 최선의 선택을 했을 때 최댓값을 구해야한다.

 

그래서, 자신의 턴인 경우에 max(좌측 점수 + dp[l + 1][r], 우측 점수 + dp[l][r - 1]) 이고,

상대의 턴인 경우에는 나의 점수를 최소화해야 하기 때문에 min(dp[l + 1][r], dp[l][r - 1]) 이다.

 

#include <iostream>
#include <cstring>
using namespace std;

int n, a[1010], dp[1010][1010];

int go(int l, int r) {

	if (l > r)return 0;
	if (dp[l][r])return dp[l][r];

	if ((n - r + l) % 2 != 0) { //1턴
		return dp[l][r] = max(a[l] + go(l + 1, r), a[r] + go(l, r - 1));
	}
	else { //2턴
		return dp[l][r] = min(go(l + 1, r), go(l, r - 1));
	}

}

int main() {

	int t; cin >> t;
	
	while (t--) {

		memset(a, 0, sizeof(a));
		memset(dp, 0, sizeof(dp));

		cin >> n;

		for (int i = 1; i <= n; i++) {
			cin >> a[i];
		}

		cout << go(1, n) << '\n';
	}
	return 0;
}