[백준] #11062 카드게임 - (DP)

문제

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

11062번: 카드 게임

목표

두 사람이 나열된 카드중 맨앞 또는 맨뒤 카드만 선택하여 높은 점수를 획득하기위한 게임에서 최고점수를 구하기

 

풀이

dp로 품. dp[turn][start][end] => 맨앞카드가 start, 맨뒤 카드가 end일경우 turn=1 즉 본인 차례인경우 얻을수 있는 최고점수 또는 turn=0 즉 상대 차례인경우 얻을수 있는 최저 점수를 저장

상대방도 최선의 방법으로 게임을 하므로 turn=0인 경우는 상대는 최고점수를 얻고 본인은 최저점수를 얻음

 

코드

#include <iostream>
#include <cstring>
#define MAX 1000 + 1

using namespace std;

int C, N;
int arr[MAX];
int dp[2][MAX][MAX];


int play(bool turn, int start, int end) {
	//turn: 게임 차례
	//start: 맨 앞 카드 .end: 맨 뒤 카드
	//start = end => 게임의 마지막 턴
	if (start == end) {
		if (turn)
			return arr[start];
		else 
			return 0;
	}
	int &ref = dp[turn][start][end];
	if (ref != -1)
		return ref;
	//본인 차례인경우: 맨앞 또는 맨뒤 카드중 가장 높은 점수를 획득할 수 있는 카드 선택
	if (turn)
		return ref = max(play(!turn, start+1, end)+arr[start], play(!turn, start, end-1)+arr[end]);
	//상대방 차례인경우: 본인차례와 마찬가지로 상대방은 최고 점수를 획득할 카드 선택=> 본인은 최소 점수 획득
	else 
		return ref = min(play(!turn, start+1, end), play(!turn, start, end-1));
}

int main() {
	cin >> C;
	for (int c=0; c<C; c++) {
		cin >> N;
		memset(dp, -1, sizeof(dp));
		for (int i=0; i<N; ++i) {
			cin >> arr[i];
		}
		cout << play(1, 0, N-1) << '\n';
	}
}