[Week 7] NUMBERGAME self review - hanjuuuuuu

[hanjuuuuuu]

NUMBERGAME self review

• 파일명: NUMBERGAME/hanjuuuuuu.cpp
• 수행시간: 4ms

1. 문제 해결 과정

왼쪽 수를 가져가는 경우, 오른쪽 수를 가져가는 경우, 왼쪽 수를 두개 지우는 경우, 오른쪽 수를 두개 지우는 경우. 이렇게 네 경우로 나누어 비교하여 최선의 방법을 구하고자 하였습니다.

2. 아이디어

재귀함수를 이용하여 반복하려고 하였습니다. 종만북 책을 참고하였습니다.

3. 코드 설명

#include <iostream>
#include <algorithm>

using namespace std;

const int EMPTY = -987654321; //답이 계산되지 않았을 때의 값
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));

    //두번째 경우(수를 2개 지우는 경우)
    if (right - left + 1 >= 2)     //수가 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 tc;
    cin >> tc;

    for (int i = 0; i < tc; i++) {
        initialize();
        cin >> boardSize;       //게임판의 숫자 개수

        for (int j = 0; j < boardSize; j++)
            cin >> board[j];

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

    return 0;
}

left와 right로 카드의 시작점과 끝점을 받습니다. left가 right보다 커지면 게임은 종료된 것이고 0을 반환합니다.
그렇지 않은 경우에는, 수를 가져가는 경우와 수를 2개 지우는 경우를 각각 처리하고 각 경우마다 left와 right을 처리해줍니다.

수를 가져가는 경우는 board의 가장 왼쪽의 점수를 가져가고 상대방이 다음부터 게임해서 얻는 최대 점수를 뺴는 것과 오른쪽 점수를 가져가는 경우 중 최대 값으로 설정합니다.

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