[algospot] NUMBERGAME

문제링크 입니다

[NUMBERGAME] 문제 😊😊😊😊😊

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

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

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

입력

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

출력

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

입력 예제

3
5
-1000 -1000 -3 -1000 -1000
6
100 -1000 -1000 100 -1000 -1000
10
7 -5 8 5 1 -4 -8 6 7 9

출력 예제

-1000
1100
7

전체 코드는 다음과 같습니다.

//
//  NUMBERGAME.cpp
//  AALGGO
//
//  Created by inhyeok on 2021/10/14.
//

#include <iostream>
#include <fstream>
#include <cstring>

using namespace std;

ifstream fin("NUMBERGAME.txt");
int n; // 테스트판의 길이.
int cache[50][50];
int board[50];
const int MIN = -50001;
// 왼쪽 1개 가져갈때.
// 오른쪽 1개 가져갈때.
// 왼쪽 두개 없앨때
// 오른쪽 두개 없앨떄
void preCalc(){
    for(int i=0; i< 50; i++){
        for(int j=0; j<50; j++){
            cache[i][j] = MIN;
        }
    }
}

int play(int left, int right){
    if(left > right) return 0;
    int &ret = cache[left][right];
    if(ret!= MIN) return ret;
    // 수를 가져가는 경우
    ret = max(board[left] - play(left+1, right), board[right] - play(left, right-1));
    //수를 없애는 경우
    if(right -left +1 >= 2){
        ret = max(ret, -play(left+2, right));
        ret = max(ret, -play(left, right-2));
    }

    return ret;
}

int main(int argc, const char * argv[]) {
    int test_case;
    fin >> test_case;

    for(int i = 0; i < test_case; i++){
        fin >> n;
        preCalc();
        memset(board, -1, sizeof(board));
        for(int j=0; j<n; j++){
            fin >> board[j];
        }
        cout << play(0, n-1) << endl;
    }
    return 0;
}