[LeetCode] 2017. Grid Game (Python)

 

난이도: Medium

 

문제 설명

---

You are given a 0-indexed 2D array grid of size 2 x n, where grid[r][c] represents the number of points at position (r, c) on the matrix. Two robots are playing a game on this matrix.

 

Both robots initially start at (0, 0) and want to reach (1, n-1). Each robot may only move to the right ((r, c) to (r, c + 1)) or down ((r, c) to (r + 1, c)).

 

At the start of the game, the first robot moves from (0, 0) to (1, n-1), collecting all the points from the cells on its path. For all cells (r, c) traversed on the path, grid[r][c] is set to 0. Then, the second robot moves from (0, 0) to (1, n-1), collecting the points on its path. Note that their paths may intersect with one another.

 

The first robot wants to minimize the number of points collected by the second robot. In contrast, the second robot wants to maximize the number of points it collects. If both robots play optimally, return the number of points collected by the second robot.

 

문제 예제

---

Example 1:

 

Input: grid = [[2,5,4],[1,5,1]]
Output: 4
Explanation: The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue.
The cells visited by the first robot are set to 0.
The second robot will collect 0 + 0 + 4 + 0 = 4 points.

Example 2:

 

Input: grid = [[3,3,1],[8,5,2]]
Output: 4
Explanation: The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue.
The cells visited by the first robot are set to 0.
The second robot will collect 0 + 3 + 1 + 0 = 4 points.

Example 3:

Input: grid = [[1,3,1,15],[1,3,3,1]]
Output: 7
Explanation:The optimal path taken by the first robot is shown in red, and the optimal path taken by the second robot is shown in blue.
The cells visited by the first robot are set to 0.
The second robot will collect 0 + 1 + 3 + 3 + 0 = 7 points.

 

제한 사항

 

---

• grid.length == 2
• n == grid[r].length
• 1 <= n <= 5 * 10^4
• 1 <= grid[r][c] <= 10^5

 

Solution(솔루션)

---

class Solution:
    def gridGame(self, grid: List[List[int]]) -> int:
        n = len(grid[0])
        prefix = [[0 for _ in range(n)] for _ in range(2)]
        prefix[0][0] = grid[0][0]
        prefix[1][0] = grid[1][0]

        for i in range(1, n):
            prefix[0][i] = prefix[0][i-1] + grid[0][i]
            prefix[1][i] = prefix[1][i-1] + grid[1][i]
        
        answer = float('inf')
        for i in range(n):
            can_blue1 = prefix[0][-1] - prefix[0][i]
            if i != 0:
                can_blue2 = prefix[1][i-1]
            else:
                can_blue2 = 0

            answer = min(answer,  max(can_blue1, can_blue2))
            
        return answer

 

prefix sum을 통해 해결했다.

 

오른쪽이랑 아래쪽으로 밖에 움직이질 못하기 때문에, 각 row마다 누적합을 구했다

예를 들어, grid = [[2,5,4], [1,5,1]]이라고 할 때, prefix = [[2, 7, 11], [1, 6, 7]]이 될 것이다.

 

다음으로, 이를 이용해 두번째 로봇이 얻을 수 있는 point를 계산했다.

두번쨰 로봇이 얻을 수 있는 값들은 다음(파란색)과 같다.

[2, 5, 4]    [2, 5, 4]    [2, 5, 4]

[1, 5, 1]    [1, 5, 1]    [1, 5, 1]

 

위 예시에서 첫번째 경우는 9, 두번째 경우는 4 또는 1, 세번째 경우는 6이다.

문제에서 두번째 로봇은 최대의 point를 먹을 것이라고 했기 때문에 두번째 경우는 4의 point를 얻을 것이다.

그렇다면 첫번째 경우 9, 두번째 경우 4, 세번째 경우 6이다. 또한 첫번째 로봇은 두번째 로봇이 최소한의 포인트를 먹게 한다고 했기때문에 9, 4, 6 중에 제일 작은 값인 4가 정답이 될 수 있다.

 

이를 코드로 구현했고 정답을 맞출 수 있었다.

---

문제: 2017. Grid Game

 

깃허브: github

algorithmPractice/LeetCode/2145-grid-game at main · laewonJeong/algorithmPractice