[Algospot] 숫자 게임 (문제 ID : NUMBERGAME)

문제

n개의 정수를 일렬로 늘어놓은 게임판을 가지고 현우와 서하가 게임을 합니다. 게임은 현우부터 시작해서 번갈아가며 진행하며, 각 참가자는 자기 차례마다 두 가지 일 중 하나를 할 수 있습니다.

• 게임판의 왼쪽 끝에 있는 숫자나 오른쪽 끝에 있는 숫자 중 하나를 택해 가져갑니다. 가져간 숫자는 게임판에서 지워집니다.

• 게임판에 두 개 이상의 숫자가 있을 경우, 왼쪽 끝에서 2개, 혹은 오른쪽 끝에서 2개를 지웁니다.

게임은 모든 숫자가 다 없어졌을 때 끝나며, 각 사람의 점수는 자신이 가져간 숫자들의 합입니다. 현우와 서하는 점수가 더 낮은 쪽이 점수 높은 쪽에 한 점 차이마다 백 원씩 주기로 내기를 했습니다. 두 사람 모두 최선을 다할 때, 두 사람의 최종 점수 차이는 얼마일까요?

 

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C <= 50) 이 주어집니다. 각 테스트 케이스의 첫 줄에는 게임판의 길이 n (1 <= n <= 50) 이 주어지며, 그 다음 줄에 n 개의 정수로 게임판의 숫자들이 순서대로 주어집니다. 각 숫자는 -1,000 에서 1,000 사이의 정수입니다.

 

출력

각 테스트 케이스마다 한 줄로, 두 사람이 최선을 다했을 때 현우가 서하보다 몇 점 더 얻을 수 있는지를 출력합니다.

---

난이도 '하'의 dp 문제이다. 그래도 풀기 쉽지 않았다. 풀고 나면 쉽지만서도 선뜻 해결방법이 떠오르지 않으니 더 정진해야겠다. 

문제는 두 사람이 최선을 다할 때 몇 점을 얻느냐이다. play라는 함수를 통해 그 값을 구한다. 인자로는 left와 right 즉 카드의 시작점과 끝점을 받는다. left가 right보다 커진다면 게임은 종료된 것이고 0을 반환한다. 아니라면 수를 가져가는 경우와 수를 없애는 두 가지 경우를 각각 처리하고 그 경우마다 왼쪽과 오른쪽을 처리해준다.

수를 가져가는 경우는 board의 제일 왼쪽의 점수에 상대방이 그 다음부터 게임해서 얻는 최대 점수를 뺴는 경우와 오른쪽 점수를 가져가는 경우 중 최대 값으로 설정한다. 

수를 없애는 경우는 수가 2개 이상일 경우만 가능하므로 right-left+1>=2를 만족할 때에만 실행한다. 결과는 마찬가지로 기본 점수와 -1을 곱한 상대방의 최대점중 더 큰 점수를 택한다.

 

코드 원본 : https://github.com/chosh95/STUDY/blob/master/Algospot/NUMBERGAME.cpp

chosh95/STUDY

C++ 코드

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int C, N;
int p[51];
int dp[51][51];
const int EMPTY = -987654321;

int play(int left, int right)
{
	if (left > right) return 0;
	int& res = dp[left][right];
	if (res != EMPTY) return res;

	res = max(p[left] - play(left + 1, right), p[right] - play(left, right - 1));
	if (right - left + 1 >= 2) {
		res = max(res, -play(left + 2, right));
		res = max(res, -play(left, right - 2));
	}
	return res;
}

int main()
{
	cin >> C;
	while (C--) {
		cin >> N;
		for (int i = 0; i < 51; i++)
			for (int j = 0; j < 51; j++) 
				dp[i][j] = EMPTY;
			
		
		for (int i = 0; i < N; i++) cin >> p[i];
		cout << play(0, N - 1) << endl;
	}
}