9.17_숫자게임_NUMBERGAME

문제 설명

 

algospot.com :: NUMBERGAME

• n개의 정수를 일렬로 늘어놓은 게임판이 있다.
• 현우와 서하가 현우부터 시작해서 번갈아가며 게임을 한다.
• 자기 차례에 두 가지 일 중 하나를 할 수 있다.
  • 게임판의 왼쪽 끝 or 오른쪽 끝 숫자 중 하나를 택해 가져간다. 가져간 숫자는 게임판에서 지워지고 가져간 사람의 점수에 추가된다.
  • 게임판에 두 개 이상의 숫자가 있을 경우, 왼쪽 끝 or 오른쪽 끝에서 2개 지운다.
• 모든 숫자가 다 없어졌을 때 게임이 끝난다.
• 두 사람 모두 자기 차례에 최선을 다한다.

=> 현우가 서하보다 몇 점을 더 얻을 수 있는지 출력하기

 

 

문제 풀이

주요 풀이

 

이 문제의 키 포인트는 "두 사람 모두 최선을 다한다."라는 부분이다.

현우가 얻을 수 있는 최고의 점수차가 아닌, 두 사람 모두 최선을 다할 때 현우가 서하보다 몇 점을 더 얻을 수 있는지를 구해야 한다.

 

두 사람이 번갈아가면서 게임을 진행하기 때문에 현재 자신의 차례에서 얻을 수 있는 최선의 결과란,

"자신의 차례에서 얻은 결과 - 다음번 차례(상대)에서 얻은 결과"가 최대인 것이 현재 얻을 수 있는 최선의 결과이다.

 

 

메모이제이션

 

정수 배열이 x ~ y까지 남아있을 때, 이 차례인 누군가가 얻을 수 있는 최대의 결과는 항상 고정적이다.

따라서 [x][y]에 따른 결과를 배열에 저장해두고 재사용하면 시간을 절약할 수 있다.

 

 

문제 풀이 코드

/*
	최선을 다 한다
	= 현재 최선의 결과를 낸다
	= "지금 결과 - 이후 결과"가 최대인 것 반환
*/

#include <iostream>
#include <string.h>

#define NCNT 50

using namespace std;

int board[NCNT];
int memo[NCNT + 1][NCNT + 1]; // startIdx, endIdx

int getMax(int a, int b) {
	if (a > b)
		return a;
	return b;
}

int doGame(int startIdx, int endIdx) {
	if (startIdx > endIdx) {
		return 0;
	}

	int& ret = memo[startIdx][endIdx];
	if (ret != -1)
		return ret;

	// case1, case2
	ret = getMax(board[startIdx] - doGame(startIdx + 1, endIdx), board[endIdx] - doGame(startIdx, endIdx - 1));

	if(startIdx < endIdx){
		// case3
		ret = getMax(-doGame(startIdx + 2, endIdx), ret);

		// case4
		ret = getMax(-doGame(startIdx, endIdx - 2), ret);
	}

	return ret;
}

int main() {
	int C;
	cin >> C;
	for (int tc = 1; tc <= C; ++tc) {
		int n;
		cin >> n;
		memset(memo, -1, sizeof(memo));
		for (int i = 0; i < n; ++i) {
			cin >> board[i];
		}
		cout << doGame(0, n - 1) << endl;
	}
	return 0;
}