leetcode 1406 - Stone Game III

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

풀이

모두가 최선을 다하기 때문에 현재 상태에서 한 개 가져갔을 때, 두 개 가져갔을 때, 세 개 가져갔을 때를 비교해서 가장 좋은 선택을 할 것이다. 세 가지 경우를 재귀적으로 반복해서 마지막까지 진행한다. 이렇게 모든 stone을 가져가서 빈 배열까지 오면 승패를 알 수 있으므로 재귀의 기저 조건으로 둘 수 있다. 이를 활용해서 d 배열을 아래와 같이 정의하고 점화식을 세우면 된다.

d[i] = stoneValue의 [i, n) 부분에서 선공했을 때 얻는 최대 이득

이렇게 정의한 후 뒤에서부터 0번째까지 d값을 구하면 현재 stoneValue에서 누가 이기는지 한 번에 알 수 있다.

 

코드

class Solution {
public:
    string stoneGameIII(vector<int>& stoneValue) {
        int n = stoneValue.size();
        vector<int> d(n+1);
        
        for(int i = n - 1; i >= 0; i--) {
            int sum = 0, best = -50000000;
            for(int j = i; j < min(i+3, n); j++) {
                sum += stoneValue[j];
                best = max(best, sum - d[j+1]);
            }
            d[i] = best;
        }

        return d[0] == 0 ? "Tie"
            : d[0] > 0 ? "Alice" : "Bob";
    }
};