1140. Stone Game II

[zeikar]

Problem link

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

Problem Summary

돌들이 있고 Alice와 Bob이 차례로 돌을 가져갈 때 최대가 되게 가져가는 점수를 구하는 문제.
1 - 2*M개의 돌을 가져갈 수 있다.

Solution

이런 게임류 문제가 익숙하지 않으면 꽤 어렵다.

dp[i][j]: i번째 돌부터 최대 j개 까지 가져갈 때의 최대 점수

이렇게 두면 좀 보일까 싶은데 쉽지 않다.

여기서 Alice와 Bob의 관계를 생각해봐야 하는데 Alice는 Bob이 최소로 가져가게 골라야 한다.
그럼 Alice가 가져가는 양은? i부터 n까지의 전체 합에서 Bob이 가져가는 양을 뺀 만큼을 가져가게 된다.

i부터 n까지의 합을 구하기 위해서는 prefix sum / suffix sum을 써서 한번에 구하면 된다.

Source Code

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:

        n = len(piles)
        prefixSum = [0] * (n + 1)
        for i in range(1, n + 1):
            prefixSum[i] = prefixSum[i - 1] + piles[i - 1]

        @cache
        def stone(idx, m):
            if idx == n:
                return 0

            ret = 0
            for x in range(0, 2 * m):
                i = idx + x
                if i < n:
                    ret = max(
                        ret,
                        prefixSum[n] - prefixSum[idx] -
                        stone(i + 1, max(x + 1, m)),
                    )
            return ret

        return stone(0, 1)