[알고스팟] 숫자 게임

문제 링크

숫자 게임

• 문제
• 답안 제출
• 통계

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • NUMBERGAME
  • 1000ms
  • 65536kb
  • 1349
  • 795 (58%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

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

어떻게 풀까?

두 명이 다 최선을 다해서 게임을 다합니다!

즉, 게임의 한 상황이 있으면, 자신이 선택하는 수는 다음 상황에서 가장 차이가 큰 수를 고를 것 입니다!

만약 어떻게 다음 상황에서 큰 수를 고르는지 궁금하시다면, 이전에 썼던 동적 계획법 강의를 봐보세용!!

링크

또한, 왼쪽과 오른쪽에서만 뽑기 때문에 게임의 상태를 가장 왼쪽에 있는 

인덱스 left와 가장 오른쪽에 있는 인덱스 right를 이용해서 나타낼 수 있습니다!

이렇게 하면, 현재 턴이 누구냐와 부분 집합 score[left][right] 배열을 이용하면, 현재 상태에서 가장 큰 점수가 몇점 인지 구할 수 있습니다.

그리고 해당 상태에서 차례인 사람이 얻을 수 있는 최대 점수를 diff(turn, l, r)이라고 합시다!

(저같은 경우는 현우가 얻을 수 있는 큰 점수는 +로 나타냈고, 서하가 얻을 수 있는 점수는 -로 나타냈습니다.)

그러면 dif(turn, l, r)의 상태는 다음 4 가지의 부분 집합 중 최대를 고르면 됩니다!

(점수판의 점수 정보는 price[]에 있다고 하겠습니다.)

위에는 max라고 썼지만, 저같은 경우는 서하가 얻을 수 있는 가장 큰 점수는 -로 나타냈기 때문에, 

서하의 경우에는 min값을 고르면 될 것입니다!

+price[]도 서하의 경우에는 -price[]가 되겠죠.

코드

#include<cstdio>
#include<cstring>
#define INF 987654321
 
enum TURN {H = 0, S = 1};
int cache[50][50][2], prices[50];
int max(int i1, int i2) {
    return i1 > i2 ? i1 : i2;
}
 
int min(int i1, int i2) {
    return i1 < i2 ? i1 : i2;
}
 
int same(int i1) {
    return i1;
}
 
int mi(int i1) {
    return -i1;
}
 
int(*cal[2])(int, int) = { max, min };
int(*conv[2])(int i1) = { same, mi };
int rets[2] = { -INF, INF };
 
int diff(int turn, int l, int r) {
    if (l > r) {
        return 0;
    }
 
    int &ret = cache[l][r][turn];
    if (ret != -1) return ret;
 
    ret = rets[turn];
 
    //cal[] : 서하의 경우엔 - 점수가 큰 점수, 따라서 min을 이용해 계산
    //          현우의 경우엔 + 점수가 큰 점수, 따라서 max를 이용해 계산
    //conv[] : 서하의 경우엔 점수를 얻으면 - 실행
    //           현우의 경우엔 점수를 얻으면 + 실행
    ret = cal[turn](ret, diff(turn ^ 1, l + 1, r) + conv[turn](prices[l])); // 왼쪽꺼 하나 떼기
    ret = cal[turn](ret, diff(turn ^ 1, l, r - 1) + conv[turn](prices[r])); //오른쪽꺼 하나 빼기
    if (r != l) {
        ret = cal[turn](ret, diff(turn ^ 1, l + 2, r)); //왼쪽꺼 두개 떼기;
        ret = cal[turn](ret, diff(turn ^ 1, l, r - 2)); // 오른쪽꺼 두개 빼기
    }
 
    return ret;
}
 
int main(){
    int t;
    scanf("%d\n", &t);
 
    while (t--) {
        memset(cache, -1, sizeof(cache));
 
        int n;
        scanf("%d\n", &n);
        for (int i = 0; i < n; i++) {
            scanf("%d \n", &prices[i]);
        }
 
        int res = diff(H, 0, n - 1);
        printf("%d\n", res);
    }
 
    return 0;
}

여담

이 문제를 다시보니, 뺄 때에도 2개를 연달아 빼고, 서로 하나씩 밖에 빼지 못하기 때문에

상태에 따라서 누가 플레이하는지가 결정된다고 하더군요!

뭔가 허무했습니다.

그리고 위와 같은 문제는 제가 풀었던 방법에서 보이듯이,

서하는 결과를 최소화 하기 위해 플레이하고, 현우는 결과를 최대화 하기 위해서 플레이를 합니다.

트리의 층마다 최대화와 최소화가 번갈아 나타난다는 의미에서 이 알고리즘을 미니맥스 알고리즘이라고 합니다!

인공지능에서 배운다고 하더군요.. -출처 : 종만북

시간복잡도는 부분 문제가 n^2이고, 부분 문제마다 4개의 연산을 하기 때문에 가 됩니다!