BOJ11062 카드 게임

BOJ11062 카드게임

두 명 모두 최선의 전략으로 임할 때 얻는 점수를 구해야 한다. 게임이론 문제

 

분명 이전에도 본 적 있는 문제인데 헷갈려서 제꼈던 문제였을 것,,

최선의 전략으로 임한다는 말을 이해하기가 어려웠다. 이해하기보단 적용하기가? 미래 예측을 기똥차게 하겠단 소린데 어디까지 생각해야 할지, 완전 끝까지 생각하려면 어떻게 구현해야 할지가 막막했다.

 

 

 

 

 

pair를 이용한 2차원 array로 풀었다.

재귀를 이용했으면 더 편했을 것도 같은데,, 구현할 때는 구할 수 있는 값부터 전체 배열을 채우는 식으로 빌드업함

 

dp[ i ][ j ] = 카드 j ~ i 로 게임을 진행할 때 { 먼저 시작한 사람의 점수, 상대방의 점수 }

 

카드 j ~ i 로 게임을 진행, X와 Y중 X가 먼저 카드를 뽑는다면

 

A. X가 카드 i 를 뽑은 후 카드 j ~ i-1 로 Y부터 게임을 진행

B. X가 카드 j 를 뽑은 후 카드 j+1 ~ i 로 Y부터 게임을 진행하는 경우가 있다.

 

X가 카드를 뽑은 후에는 Y부터 게임을 진행하므로

X가 i, j를 뽑는 경우 X, Y가 각각 얻게 되는 점수는 아래와 같다.

 

A. X가 카드 i 를 선택

  X: dp[ i-1 ][ j ].second + Card[ i ]

  Y: dp[ i-1 ][ j ].first

 

B. X가 카드 j 를 선택

  X: dp[ i ][ j+1 ].second + Card[ j ]

  Y: dp[ i ][ j+1 ].first

 

X는 최선의 전략으로 임해야하므로,

A와 B중 이기는 경우를,

둘 다 이기거나 둘 다 지는 경우 점수가 더 큰 경우를 고른다.

 

 

빌드업 할 거기 때문에 처음에 카드에 적힌 값들을 입력받을 때

dp[ i ][ i ]={ Card[ i ], 0 }로 하고

dp[ 1 ][ 0 ]~dp[ N-1 ][ N-2 ]부터 dp[ N-1 ][ 0 ]까지 채워주면 되겠다.

 

마지막에 dp[ N-1 ][ 0 ].first를 출력

 

 

 

 

 

코드

//Card Game
#include <cstdio>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;


//dp[i][j]: the best score pair playing with card j~i
pair<int,int> dp[1000][1000];
int main() {
	int T, N, c[1000];

	scanf("%d", &T);
	while (T--) {
		scanf("%d", &N);
		for (int i = 0; i < N; ++i) scanf("%d", &c[i]), dp[i][i] = { c[i],0 };
	
		for (int n = 1; n < N; ++n) {
			for (int i = n, j = 0; i < N; ++i, ++j) {
				pair<int, int> A = { c[i] + dp[i - 1][j].second, dp[i - 1][j].first };
				pair<int, int> B = { c[j] + dp[i][j + 1].second, dp[i][j + 1].first };

				if (A.first < A.second) {
					if (B.first >= B.second) dp[i][j] = B;
					else if (B.first > A.first) dp[i][j] = B;
					else dp[i][j] = A;
				}
				else {
					if (B.first < B.second) dp[i][j] = A;
					else if (A.first > B.first) dp[i][j] = A;
					else dp[i][j] = B;
				}

			}
		}
//		for (int i = 0; i < N; ++i) {
//			for (int j = 0; j <= i; ++j)
//				printf("%d:%d  ", dp[i][j].first, dp[i][j].second);
//			printf("\n");
//		}
		printf("%d\n", dp[N - 1][0].first);
	}
	return 0;
}

 

난 이해가 안 돼

 

1. 왜 dp[ i ][ j ]를 i부터 j까지로 안 두고 j부터 i까지로 뒀는지 모르겠다;; 적어놓으려고 다시 열어보니 출력하는 게 dp[ 0 ][ N-1 ]이 아니라 당황 대체 왜 그랬던 것인지,,,?,,,???

2. 도대체 typedef는 써놓고 왜 pair<int,int>를 수고스럽게 쓴 것인지.........도대체 무슨 정신이었는지........