Leetcode 1872. Stone Game VIII

문제

Alice and Bob take turns playing a game, with Alice starting first.

There are n stones arranged in a row. On each player's turn, while the number of stones is more than one, they will do the following:

Choose an integer x > 1, and remove the leftmost x stones from the row.
Add the sum of the removed stones' values to the player's score.
Place a new stone, whose value is equal to that sum, on the left side of the row.
The game stops when only one stone is left in the row.

The score difference between Alice and Bob is (Alice's score - Bob's score). Alice's goal is to maximize the score difference, and Bob's goal is the minimize the score difference.

Given an integer array stones of length n where stones[i] represents the value of the ith stone from the left, return the score difference between Alice and Bob if they both play optimally.

Alice와 Bob이 번갈아가며 게임을 진행하며, Alice가 먼저 시작합니다.

일렬로 놓인 n개의 돌이 있습니다. 각 플레이어는 자신의 차례에 돌의 개수가 1개보다 많다면 다음 행동을 합니다.

1. x > 1인 정수 x를 하나 선택하고, 왼쪽에서부터 x개의 돌을 제거합니다.
2. 제거한 돌들의 값의 합을 자신의 점수에 더합니다.
3. 제거한 돌들의 값의 합과 동일한 값을 가지는 새로운 돌 하나를 만들어, 돌의 맨 왼쪽에 놓습니다.

돌이 하나만 남으면 게임이 종료됩니다.

Alice와 Bob의 점수 차이는 다음과 같이 정의됩니다.

Alice의 점수 - Bob의 점수

Alice는 이 점수 차이를 최대한 크게 만드는 것이 목표이고, Bob은 점수 차이를 최대한 작게 만드는 것이 목표입니다.

길이가 n인 정수 배열 stones가 주어집니다.

stones[i]는 왼쪽에서부터 i번째 돌의 값을 의미합니다.

Alice와 Bob이 모두 최적으로 플레이할 때, 최종적으로 얻어지는 Alice와 Bob의 점수 차이를 반환하세요.

---

예시

입력: stones = [-1,2,-3,4,-5]
출력: 5

설명:

• Alice는 처음 4개의 돌을 제거합니다.

  • 제거한 돌의 합은 (-1) + 2 + (-3) + 4 = 2입니다.
  • Alice의 점수에 2를 더하고, 값이 2인 새로운 돌을 맨 왼쪽에 놓습니다.
  • 따라서 돌의 상태는 stones = [2,-5]가 됩니다.

• Bob은 처음 2개의 돌을 제거합니다.

  • 제거한 돌의 합은 2 + (-5) = -3입니다.
  • Bob의 점수에 -3을 더하고, 값이 -3인 새로운 돌을 맨 왼쪽에 놓습니다.
  • 따라서 돌의 상태는 stones = [-3]가 됩니다.

돌이 하나만 남았으므로 게임이 종료됩니다.

최종 점수 차이는

Alice의 점수 - Bob의 점수
= 2 - (-3)
= 5

따라서 정답은 5입니다.

---

제한

• $n == stones.length$
• $2 <= n <= 10^5$
• $-10^4 <= stones[i] <= 10^4$

---

풀이

앨리스와 밥이 점수를 얻는 구조를 처음 보면 꽤 복잡해 보이지만, 생각보다 단순하다.

처음 앨리스가 2개 이상의 돌을 골라 점수를 얻고, 그 합을 새로운 맨 앞의 돌로 만든다고 생각해보자.

이후 밥이 몇 개의 돌을 더 고른다면 밥이 얻게 되는 점수는

앨리스가 이전에 합친 값 + 밥이 새롭게 포함한 돌들의 합

이 된다.

즉, 각 턴에서 얻을 수 있는 값은 결국 원래 배열의 prefix sum과 정확히 동일하다.

이를 이용하면 prefix sum을 기반으로 다음과 같이 DP를 구현할 수 있다.

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        N = len(stones)
        prefix = [0] * N
        prefix[0] = stones[0]

        for i in range(1, N):
            prefix[i] = prefix[i - 1] + stones[i]

        @cache
        def dp(index: int) -> int:
            if index == N - 1:
                return prefix[index]

            return max(dp(index + 1), prefix[index] - dp(index + 1))

        return dp(1)

여기서 dp(index)는 index 이후의 선택에서 현재 플레이어가 얻을 수 있는 최대 점수 차이를 의미한다.

현재 prefix[index]를 선택하지 않는다면 dp(index + 1)이 되고, 현재 값을 선택한다면 prefix[index]를 얻은 뒤 상대가 dp(index + 1)만큼의 점수 차이를 가져가므로

prefix[index] - dp(index + 1)

이 된다.

따라서 두 경우 중 더 큰 값을 선택하면 된다.

여기서 조금 더 최적화하여 바텀업 방식으로 구현하면 다음과 같다.

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        N = len(stones)
        prefix = [0] * N
        prefix[0] = stones[0]

        for i in range(1, N):
            prefix[i] = prefix[i - 1] + stones[i]

        dp = [0] * N
        dp[-1] = prefix[-1]

        for i in range(N - 2, 0, -1):
            dp[i] = max(dp[i + 1], prefix[i] - dp[i + 1])

        return dp[1]

이 점화식을 보면 dp[i]를 계산할 때 사용하는 값은 오직 dp[i + 1]뿐이다.

따라서 DP 배열 전체를 저장할 필요 없이 하나의 변수만 유지하는 방식으로 다시 최적화할 수 있다.

class Solution:
    def stoneGameVIII(self, stones: List[int]) -> int:
        N = len(stones)

        prefix = [0] * N
        prefix[0] = stones[0]

        for i in range(1, N):
            prefix[i] = prefix[i - 1] + stones[i]

        val = prefix[-1]

        for i in range(N - 2, 0, -1):
            val = max(val, prefix[i] - val)

        return val

결과적으로 시간 복잡도는 O(N)이며, DP에 필요한 추가 공간은 O(1)까지 줄일 수 있다.