그리드 게임

크기가 grid 인 0-인덱스 2D 배열2 x n이 주어집니다. 여기서 grid[r][c]는 행렬의 위치(r, c)에 있는 점의 수를 나타냅니다. 두 로봇이 이 매트릭스에서 게임을 하고 있습니다.

두 로봇 모두 처음에 (0, 0)에서 시작하여 (1, n-1)에 도달하려고 합니다. 각 로봇은 오른쪽((r, c)에서 (r, c + 1)으로) 또는 아래로((r, c)에서 (r + 1, c)로)만 이동할 수 있습니다.

게임이 시작될 때 첫 번째 로봇은 (0, 0)에서 (1, n-1)로 이동하여 경로에 있는 셀에서 모든 포인트를 수집합니다. 경로를 통과하는 모든 셀(r, c)에 대해 grid[r][c]는 0로 설정됩니다. 그런 다음 두 번째 로봇은 (0, 0)에서 (1, n-1)로 이동하여 경로에서 포인트를 수집합니다. 경로가 서로 교차할 수 있습니다.

첫 번째 로봇은 두 번째 로봇이 수집하는 포인트 수를 최소화하려고 합니다. 반대로 두 번째 로봇은 수집하는 포인트 수를 최대화하려고 합니다. 두 로봇 모두 최적의 상태로 플레이하면 두 번째 로봇이 수집한 점수를 반환합니다.

예 1:



입력: 그리드 = [[2,5,4],[1,5,1]]
출력: 4
설명: 첫 번째 로봇이 선택한 최적 경로는 빨간색으로 표시되고 두 번째 로봇이 선택한 최적 경로는 파란색으로 표시됩니다.
첫 번째 로봇이 방문한 셀은 0으로 설정됩니다.
두 번째 로봇은 0 + 0 + 4 + 0 = 4점을 수집합니다.

예 2:



입력: 그리드 = [[3,3,1],[8,5,2]]
출력: 4
설명: 첫 번째 로봇이 선택한 최적 경로는 빨간색으로 표시되고 두 번째 로봇이 선택한 최적 경로는 파란색으로 표시됩니다.
첫 번째 로봇이 방문한 셀은 0으로 설정됩니다.
두 번째 로봇은 0 + 3 + 1 + 0 = 4점을 수집합니다.

예 3:



입력: 그리드 = [[1,3,1,15],[1,3,3,1]]
출력: 7
설명: 첫 번째 로봇이 선택한 최적 경로는 빨간색으로 표시되고 두 번째 로봇이 선택한 최적 경로는 파란색으로 표시됩니다.
첫 번째 로봇이 방문한 셀은 0으로 설정됩니다.
두 번째 로봇은 0 + 1 + 3 + 3 + 0 = 7점을 수집합니다.

제약:

grid.length == 2

n == grid[r].length

1 <= n <= 5 * 104

1 <= grid[r][c] <= 105

해결책:

class Solution:
    def gridGame(self, grid: List[List[int]]) -> int:
        n = len(grid[0])
        top = [0]
        bottom = [0]
        for el in grid[0]:
            top.append(top[-1] + el)
        for el in grid[1]:
            bottom.append(bottom[-1] + el)
        opponent = float('inf')
        mindex = None
        for i in range(n):
            curropp = max(top[-1] - top[i + 1], bottom[i])
            if curropp <= opponent:
                opponent = curropp
                mindex = i
        return max(top[-1] - top[mindex + 1], bottom[mindex])