leetcode 1563 - Stone Game V

https://leetcode.com/problems/stone-game-v/

풀이

Alice가 임의의 크기로 left와 right를 나눠서 더 작은 쪽의 점수를 얻으면, 그 뒤로 더 작은 쪽에서 같은 게임이 반복된다. 따라서 모든 크기로 나눠보고 재귀적으로 게임을 진행시킬 수 있다. 이 게임은 마지막 하나가 남을 때까지 진행되며 그 상태에서 Alice는 0점을 얻는다. 

 

모든 subgame은 stoneValue의 subarray에서 이루어지기 때문에 중복된 연산을 방지하기 위해 아래와 같이 d 배열을 정의한다.

d[i][j] = stoneValue의 [i, j] 부분에서 게임할 때 Alice가 얻는 최대 점수

 

매 subgame에서 가능한 경우를 탐색할 때 미리 구해놓은 sum 배열을 활용하면 좀 더 효율적으로 구할 수 있다.

 

 

코드

class Solution {
public:
    vector<vector<int>> d;
    vector<int> sum;
    int stoneGameV(vector<int>& stoneValue) {
        int n = stoneValue.size();
        d.resize(n, vector<int>(n, -1));
        sum.resize(n+1);
        
        for(int i = 0; i < n; i++) {
            sum[i+1] = sum[i] + stoneValue[i];
        }
        
        return dfs(0, n-1);
    }
    
    int dfs(int start, int end) {
        if(d[start][end] != -1) return d[start][end];
        if(start == end) return d[start][end] = 0;
    
        int best = 0;
        for(int i = start; i < end; i++) {
            int leftSum = sum[i+1] - sum[start];
            int rightSum = sum[end+1] - sum[i+1];

            if(leftSum < rightSum) {
                best = max(best, leftSum + dfs(start, i));
            } else if(leftSum > rightSum) {
                best = max(best, rightSum + dfs(i+1, end));
            } else {
                best = max(best, max(leftSum + dfs(start, i), rightSum + dfs(i+1, end)));
            }
        }
        return d[start][end] = best;
    }
};