숫자 게임

문제 : https://algospot.com/judge/problem/read/NUMBERGAME

문제

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

• 게임판의 왼쪽 끝에 있는 숫자나 오른쪽 끝에 있는 숫자 중 하나를 택해 가져갑니다. 가져간 숫자는 게임판에서 지워집니다.
• 게임판에 두 개 이상의 숫자가 있을 경우, 왼쪽 끝에서 2개, 혹은 오른쪽 끝에서 2개를 지웁니다.

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

코드 ( C+ + ) 종만북 참조

#include <iostream>

#include <string>

#include <algorithm>

#include <vector>

using namespace std;

int board[50];

int cache[50][50];

const int EMPTY = -987654321;

int solve(int left, int right) {

if (left > right) return 0;

int& ret = cache[left][right];

if (ret != EMPTY)

return ret;

ret = max(ret, board[left] - solve(left + 1 , right));

ret = max(ret, board[right] - solve(left, right - 1));

if (right - left + 1 >= 2) {

ret = max(ret, -solve(left + 2, right));

ret = max(ret, -solve(left, right - 2));

}

return ret;

}

int main()

{

int C;

cin >> C;

while (C--) {

int N;

cin >> N;

for (int i = 0; i < N; i++) {

cin >> board[i];

for (int j = i; j < N; j++)

{

cache[i][j] = EMPTY;

}

}

int ans = solve(0, N - 1);

cout << ans << endl;

}

return 0;

}