[NUMBERGAME] 숫자게임

[NUMBERGAME] 숫자게임 : https://algospot.com/judge/problem/read/NUMBERGAME

< 소스코드 >

gameNum(s, e) : (s, e) 까지 최선을 다해 게임을 했을 때, 서하점수-현우점수의 최대값.

#include <stdio.h>
#include <string.h>
 
const int INF = 1e9;
 
int a[51];
int d[51][51];
 
int max(int a, int b)
{
    return a > b ? a : b;
}
 
int gameNum(int s, int e)
{
    int ret=0;
    if(s == e) return a[s];
    if(s > e) return 0;
    if(d[s][e] != INF) return d[s][e];
 
    ret = max(a[s]-gameNum(s+1, e), a[e]-gameNum(s, e-1));
    if(e-s >= 1) ret = max(ret, -gameNum(s+2, e));
    if(e-s >= 1) ret = max(ret, -gameNum(s, e-2));
 
    return d[s][e] = ret;
}
 
int main()
{
    int tc;
    scanf("%d", &tc);
 
    while(tc--) {
        int n;
        scanf("%d", &n);
 
        for(int i=0; i<n; i++) {
            scanf("%d", a+i);
            for(int j=0; j<n; j++) 
                d[i][j] = INF;
        }
 
        
        printf("%d\n", gameNum(0, n-1));
    }
    return 0;
}
 

>> 재귀적으로 함수를 호출하는 과정에서 음수처리 한 부분에 주목.

>> 현우부터 게임을 시작하고, 현우가 서하보다 몇점을 더 얻을수 있는지 알아야 하기에..

>> 첫번째 턴에서 현우가 가진 점수는 그대로 현우의 점수가 된다. 두번째 턴에서 서하가 가진 점수는 현우의 점수에서 빼주면 그것이 그대로 차이가 된다.