[백준] #11062 카드게임

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

i009727 2020. 3. 11. 19:25

문제

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

11062번: 카드 게임

문제 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 카드나 가장 오른쪽에 있는 카드를 가져갈 수 있다. 카드가 더 이상 남아있지 않을 때까지 턴은 반복된다. 게임의 점수는 자신이 가져간 카드에 적힌 수의 합이다. 근우와 명우는 서로 자신의 점수를 가장 높이기 위해 최선의 전략으로 게임에 임한다. 놓여있는 카드의 개수

www.acmicpc.net

목표

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

풀이

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';
	}
}