백준 11062번 카드 게임 C++

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

11062번: 카드 게임

 

누가봐도 나 DP에요! 

 

소리치고 있는 문제이다. 다만 아이디어를 떠올리기는 쉽지 않았다. 

 

1 2 3 4번 인덱스가 있을 때 난 dp[1] dp[4] 를 만들어서 왼쪽을 선택시, 오른쪽을 선택시를 고려해서 고르는 것을 택했다. 그러나 이것은 정답이 아니었고..

 

2차원 배열을 사용하는 것이 정답이었다.

 

dp[x][y] 라고 할 때 x번~y번이 인덱스에서 최댓값을 가지고 있으면 된다. 

그리고 문제 조건에서 근우의 최대 점수를 구하는 것이기 때문에 근우의 최선은 명우의 최소가 된다.

 

문제에서 계속 둘 다 열심히한다고 하기 때문에 이것을 떠올리기 힘들다. 

 

그러므로 근우의 턴에서는 max를 , 명우의 턴에서는 min으로 가는 것이 정답으로 가는 길이다. 

 

#include <iostream>
#include <vector>
#include <cstring>

#define MAX 1001
using namespace std;

vector<int> arr;
int dp[MAX][MAX];
int n;

int reccusion(int x, int y, int cnt) {
	if (x > y) return 0;
	else if (dp[x][y] != 0) return dp[x][y];
	else {
		if (cnt % 2 == 0) {
			return dp[x][y] = max(arr[x] + reccusion(x + 1, y, cnt + 1), arr[y] + reccusion(x, y - 1, cnt + 1));
		}
		else {
			return dp[x][y] = min(reccusion(x + 1, y, cnt + 1), reccusion(x, y - 1, cnt + 1));
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int T; cin >> T;

	for (int t = 0; t < T; t++) {
		int N; cin >> N;
		
		n = N;
		
		arr = vector<int>(N);
		int answer = 0;
		for (int i = 0; i < N; i++) {
			cin >> arr[i];
		}
		memset(dp, 0, sizeof dp);

		cout << reccusion(0, N - 1, 0) << '\n';
	}
}