486. Predict the Winner

Description

You are given an integer array nums. Two players are playing a game with this array: player 1 and player 2.

Player 1 and player 2 take turns, with player 1 starting first. Both players start the game with a score of 0. At each turn, the player takes one of the numbers from either end of the array (i.e., nums[0] or nums[nums.length - 1]) which reduces the size of the array by 1. The player adds the chosen number to their score. The game ends when there are no more elements in the array.

Return true if Player 1 can win the game. If the scores of both players are equal, then player 1 is still the winner, and you should also return true. You may assume that both players are playing optimally.

Example 1:

Input: nums = [1,5,2]
Output: false
Explanation: Initially, player 1 can choose between 1 and 2.
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.
Hence, player 1 will never be the winner and you need to return false.

Example 2:

Input: nums = [1,5,233,7]
Output: true
Explanation: Player 1 first chooses 1. Then player 2 has to choose between 5 and 7. No matter which number player 2 choose, player 1 can choose 233.
Finally, player 1 has more score (234) than player 2 (12), so you need to return True representing player1 can win.

Constraints:

• 1 <= nums.length <= 20
• 0 <= nums[i] <= 10^7

---

처음에 어떤 식으로 접근해야 할지 고민을 많이 했습니다. 특히 문제 설명에서 표현했듯이 (You may assume that both players are playing optimally.) 두 플레이어가 최적의 플레이를 한다고 가정하는 것을 코드로 어떻게 표현해야 할 지가 가장 고민이었습니다.

중앙부터 거꾸로 이동하는 등의 접근 방법이 적용되지 않아서 한참 고민하다가 블로그를 참고했습니다.(https://medium.com/algorithms-digest/predict-the-winner-16668e9c1cb8)

핵심은 dp로 접근해 전체 배열을 작은 부분부터 계산해 플레이어의 최적의 점수를 찾아내는 것이었습니다.

---

예를 들어서 해결방법을 설명드리겠습니다.

예제의 nums는 nums = [1, 3, 52, 4, 9] 라고 가정하겠습니다.

사전 준비

먼저, 2차원 배열의 dp 배열을 생성해주겠습니다.

dp = [[0 for _ in range(n)] for _ in range(n)] 해당 dp 배열은 부분 배열에서 Player1이 가질 수 있는 최대 점수를 기록할 때 사용합니다.

dp[start][end] 의 값은 부분 배열(nums[start : end])에서 Player1이 가질 수 있는 최대 점수를 의미합니다.

그리고, 누적합을 계산한 1차원 cumSum 배열을 생성해주겠습니다.

cumSum = [0 for _ in range(n)]
for i in range(n):
	if i == 0:
		cumSum[i] = nums[i]
	else:
		cumSum[i] = cumSum[i - 1] + nums[i]

cumSum 배열은 부분 배열의 전체 점수를 계산하는데 사용됩니다.

---

dp 계산

배열에 원소 개수가 하나일 때, Player1의 최대 점수는 해당 원소입니다.

nums[0:0] 에서의 최대 점수는 1이고, nums[1:1] 에서의 최대 점수는 3, nums[2:2] 에서의 최대 점수는 52입니다. 이렇게 반복해줍니다.

dp는 이렇게 기록됩니다.
[1, 0, 0, 0, 0]
[0, 3, 0, 0, 0]
[0, 0, 52, 0, 0]
[0, 0, 0, 4, 0]
[0, 0, 0, 0, 9]

배열에 원소 개수가 둘일 때, Player1의 최대 점수는 그 두개의 원소 중 큰 값입니다.

nums[0:1] 에서의 최대 점수는 3이고, nums[1:2] 에서의 최대 점수는 52, nums[2:3] 에서의 최대 점수는 52입니다. 이렇게 반복해줍니다.

dp는 이렇게 기록됩니다.
[1, 3, 0, 0, 0]
[0, 3, 52, 0, 0]
[0, 0, 52, 52, 0]
[0, 0, 0, 4, 9]
[0, 0, 0, 0, 9]

배열에 원소 개수가 셋일 때부터 미리 계산해놓은 dp의 값을 사용할 수 있습니다.
1. Player1이 첫 번째 원소를 선택했다고 가정합니다.
2. 나머지 2개의 원소에 대해서는 이전에 미리 최대 점수를 구해놓았습니다. Player2는 해당 최대 점수를 가집니다.
3. Player1은 남은 배열의 전체 점수에서 최대 점수를 뺀 값을 가집니다.

Player1이 마지막 원소를 선택했다고 가정하고 반대로도 진행합니다.

이것을 코드로 아래와 같이 변경할 수 있습니다.

choice_1 = nums[start] + (cumSum[end] - cumSum[start + 1] + nums[start + 1] - dp[start + 1][end])
choice_2 = nums[end] + (cumSum[end - 1] - cumSum[start] + nums[start] - dp[start][end - 1])
dp[start][end] = max(choice_1, choice_2)

dp는 이렇게 기록됩니다.
[1, 3, 53, 0, 0]
[0, 3, 52, 7, 0]
[0, 0, 52, 52, 56]
[0, 0, 0, 4, 9]
[0, 0, 0, 0, 9]

이제 원소가 4개일 때도, 5개일 때도 이전의 계산 값을 이용해 Player1의 최대 점수를 구할 수 있습니다.

이 과정을 반복하면, 결국 전체 배열의 점수가 dp[0][n-1](n은 nums 배열의 길이)에 기록됩니다.

마지막으로, dp[0][n-1]의 값이 전채 배열 크기의 절반보다 큰지 확인합니다. 크거나 같다면 Player1의 승리로 True, 아니라면 False의 값을 반환하면 됩니다.

전체 코드는 다음과 같습니다.

class Solution:
    def predictTheWinner(self, nums: List[int]) -> bool:
        n = len(nums)
        
        # 누적합 배열을 생성합니다.
        cumSum = [0 for _ in range(n)]
        for i in range(n):
            if i == 0:
                cumSum[i] = nums[i]
            else:
                cumSum[i] = cumSum[i - 1] + nums[i]
        
        # 2차원 DP 배열을 생성합니다.
        dp = [[0 for _ in range(n)] for _ in range(n)]
        
        # 부분 배열의 길이를 점점 늘려나가며 계산합니다.
        for i in range(n):
            for j in range(n - i):
                start = j
                end = i + j
                
                # 부분 배열의 원소가 1개일 때
                if start == end:
                    dp[start][end] = nums[start]
                # 부분 배열의 원소가 2개일 때
                elif start + 1 == end:
                    dp[start][end] = max(nums[start], nums[end])
                # 부분 배열의 원소가 3개 이상일 때
                else:
                    choice_1 = nums[start] + (cumSum[end] - cumSum[start + 1] + nums[start + 1] - dp[start + 1][end])
                    choice_2 = nums[end] + (cumSum[end - 1] - cumSum[start] + nums[start] - dp[start][end - 1])
                    dp[start][end] = max(choice_1, choice_2)
        
        # Player1이 가질 수 있는 점수가 전체 점수 합의 1/2 이상인지 확인합니다.
        return dp[0][n - 1] >= (cumSum[n - 1] - dp[0][n - 1])

---

알고리즘은 항상 어렵습니다,, 쉬워지는 날까지.

궁금하신 점이나 의견이 있으시면 언제든 말씀주시면 감사하겠습니다. :)