algospot NUMBERGAME

문제 링크입니다: https://algospot.com/judge/problem/read/NUMBERGAME

틱택토 문제(http://jaimemin.tistory.com/377?category=985009)와 구조적으로 유사한 문제입니다.

재귀함수가 얼마나 강력한지 확인할 수 있었던 문제였습니다.

/*

n개의 정수를 일렬로 늘어놓은 게임판을 가지고 현우와 서하가 게임을 한다.

게임은 현우부터 시작해서 번갈아가며 진행하며, 각 참가자는 자기 차례마다 두 가지 일 중 하나를 할 수 있다.

 

1.게임판의 왼쪽 끝에 있는 숫자나 오른쪽 끝에 있는 숫자 중 하나를 택해 가져간다.

  가져간 숫자는 게임판에서 지워진다.

2.게임판에 두 개 이상의 숫자가 있을 경우, 왼쪽 끝에서 2개, 혹은 오른쪽 끝에서 2개를 지운다.(가져가지 않고 지우기만 한다)

 

게임은 모든 숫자가 다 없어졌을 때 끝나며, 각 사람의 점수는 자신이 가져간 숫자들의 합!

현우와 서하는 점수가 더 낮은 쪽이 점수 높은 쪽에 한 점 차이마다 백 원씩 주기로 내기를 했다.

두 사람 모두 최선을 다할 때, 두 사람의 최종 점수 차이는?

*/

#include <iostream>

#include <algorithm>

using namespace std;

 

const int EMPTY = -987654321; //답의 범위가 -50000~50000

int board[50], boardSize; //boardSize 최대 50

int cache[50][50];

 

int play(int left, int right)

{

        //기저 사례: 모든 수가 다 없어졌을 때

        if (left > right)

               return 0;

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

        if (result != EMPTY)

               return result;

        //첫번째 경우

        result = max(board[left] - play(left + 1, right), board[right] - play(left, right - 1));

        //두번째 경우

        if (right - left + 1 >= 2)

        {

               result = max(result, -play(left + 2, right)); //왼쪽 두개 지우는 경우

               result = max(result, -play(left, right - 2)); //오른쪽 두개 지우는 경우

        }

        return result;

}

 

void initialize(void) //cache 초기화

{

        for (int i = 0; i < 50; i++)

               for (int j = 0; j < 50; j++)

                       cache[i][j] = EMPTY;

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case < 0 || test_case>50)

               exit(-1);

 

        for (int i = 0; i < test_case; i++)

        {

               initialize();

               cin >> boardSize;

               if (boardSize < 1 || boardSize>50)

                       exit(-1);

              

               for (int j = 0; j < boardSize; j++)

                       cin >> board[j];

 

               cout << play(0, boardSize-1) << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략