백준11062 카드 게임

작성일 | In

문제 링크

  • http://icpc.me/11062

문제 출처

  • 2015 ACM-ICPC 대전 인터넷 예선 B번

사용 알고리즘

  • 알고리즘 게임
  • DP

시간복잡도

  • O(n2)

풀이

근우와 명우는 서로 번갈아가면서 카드를 가져가는데, 각 턴마다 왼쪽 혹은 오른쪽 카드 중 하나를 선택해 가져갑니다.
서로 최적의 플레이를 했을 때, 근우가 얼마나 많은 점수를 얻을 수 있는지를 구해야 하는 문제입니다.

가장 기본적으로는 완전 탐색을 돌리면서 근우의 턴에서는 근우의 점수가 최대가 되게, 명우의 턴에서는 근우의 점수가 최소가 되게 플레이하는, 흔히 말해 minimax tree를 그리면 쉽게 해결할 수 있습니다.

int f(int i, int j, bool flag) 를 왼쪽에서 가져간다면 i번째 카드, 오른쪽에서 가져간다면 j번째 카드를 가져가야 하는 상황에서 근우가 얻을 수 있는 최대 점수라고 정의를 합시다. 또한, flag를 이용해 현재 누구의 턴인지 구분을 해줍시다.
완전탐색으로 코드를 짜면 아래와 같습니다.

1
2
3
4
5
6
7
8
9
10
11
int solve(int i, int j, int flag){
	if(i >= j){
		if(!flag) return cost[i];
		else return 0;
	}
	if(!flag){ //gnu
		return max(solve(i+1, j, !flag) + cost[i], solve(i, j-1, !flag) + cost[j]);
	}else{
		return min(solve(i+1, j, !flag), solve(i, j-1, !flag));
	}
}

근우의 턴에서는 근우의 점수를 최대화 시켜야 하고, 명우의 턴에서는 근우의 점수를 최소화 시키는 것이 서로 최적의 플레이를 하는 것입니다.

위 코드로 탐색을 진행하면 O(2n) 복잡도가 나오고, N 범위가 최대 1000이기 때문에 가볍게 시간초과가 나게 됩니다.
만약 i, j, flag의 값이 동일하다면, 그 상황에 대해 언제 계산하든 일정한 값이 나옵니다. 흔히 참조적 투명성이 보장된다고 합니다.
이 특징을 이용해 memoization을 수행해주면 상태 공간은 n*n*2개이며, 각 상태에 대해 상수시간 안에 해를 구할 수 있습니다. 그러므로 O(n2)만에 문제를 해결할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> p;

int dp[1010][1010][2];

int cost[1010];

int solve(int i, int j, int flag){
	int &ret = dp[i][j][flag];
	if(ret != -1) return ret;
	if(i >= j){
		if(!flag) return ret = cost[i];
		else return ret = 0;
	}
	if(!flag){ //gnu
		return ret = max(solve(i+1, j, !flag) + cost[i], solve(i, j-1, !flag) + cost[j]);
	}else{
		return ret = min(solve(i+1, j, !flag), solve(i, j-1, !flag));
	}
}

void f(){
	memset(dp, -1, sizeof(dp));
	int n; cin >> n;
	for(int i=1; i<=n; i++) cin >> cost[i];

	cout << solve(1, n, 0) << "\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while(t--) f();
}