Intuition

optimally하게 play하는 것이 이 문제에서 가장 관건이었다.
처음에는 greedy하게 시도했으나, optimal한 플레이를 할 수 없었다. 이를 재귀를 통해 모든 경우의 수를 끝까지 살펴보고 leaf node에서 top으로 올라오는 과정에서 더 큰 점수를 얻는 경우를 택하는 것을 고려해 볼 수 있다.

Approach

점화식부터 작성해보겠다.
각각 player1의 턴이냐, 2의 턴이냐에 따라 점수를 누적할 변수가 2개 필요하지 않도록(2개인 경우 재귀의 값 반환과정에서 복잡해짐), 하나의 변수에 player1의 점수는 +로, 2의 점수는 -로 계산한다. 마지막 결과값이 양수이면 player1의 승리다.

케이스는 앞의 것을 가져가느냐, 뒤의 것을 가져가느냐 두 가지로 나뉜다.
player1과 2의 구분은 turn 의 값을 1로 하느냐 -1로 하느냐로 결정한다.

...

bool predictTheWinner(int* nums, int numsSize) {
    return predict(0,numsSize-1,1,nums)>=0;
}

int predict(int s, int e, int turn, int* nums){
    int a=0,b=0;
    if (s==e) return turn*nums[s];

    a=turn*nums[s]+predict(s+1,e,turn*-1,nums);
    b=turn*nums[e]+predict(s,e-1,turn*-1,nums);

    return ...;
}

값을 반환하는 과정에서 player1의 턴이라면 두 케이스 중 더 큰 값을 반환해야 player1에게 이득일 것이고, player2의 턴이라면 더 작은 값을 반환해야 player2에게 이득일 것이다.

if (turn==1) return MAX(a,b);
else return MIN(a,b);

Solution

#define MAX(a,b) ((a)>=(b)?(a):(b))

bool predictTheWinner(int* nums, int numsSize) {
    return predict(0,numsSize-1,1,nums)>=0;
}

int predict(int s, int e, int turn, int* nums){
    int a=0,b=0;
    if (s==e) return turn*nums[s];

    a=turn*nums[s]+predict(s+1,e,turn*-1,nums);
    b=turn*nums[e]+predict(s,e-1,turn*-1,nums);

    return turn*MAX(turn*a,turn*b); // MAX만을 이용하여 MIN을 함께 구현하는 방법
}

Complexity

Time Complexity

$O(N^2)$

Space Complexity

$O(N)$

지적 및 질문 환영