2017. Grid Game (JAVA)

출처 : https://leetcode.com/problems/grid-game/description/?envType=daily-question&envId=2025-01-21

문제

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.

 

0-인덱스 2D 배열 grid가 주어집니다. 이 배열은 크기가 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)로 이동하며 경로에 있는 점수를 수집합니다. 이때 두 로봇의 경로는 서로 겹칠 수 있습니다.

첫 번째 로봇은 두 번째 로봇이 수집하는 점수를 최소화하려고 하고, 두 번째 로봇은 자신이 수집하는 점수를 최대화하려고 합니다. 두 로봇이 최적으로 플레이할 때, 두 번째 로봇이 수집하는 점수의 합을 반환하세요.

 

 

접근 : Prefix

 

로봇은 반드시 좌측 또는 아래로 이동하므로 로봇1이 지나간 이후에 로봇2가 최대값을 가지기위해서는 반드시 2가지 방식중에서 한가지 방식을 골라야함

 

즉, 로봇2의 최댓값은 로봇1이 아래로이동한 열을 기준으로 좌측하단의 합, 우측상단의 합 둘 중 더 큰값이다.

 

1, 2행의 누적합을 구한뒤 0~n-1 열을 탐색하며 로봇2의 값을 갱신해나가면 문제를 해결할수있다.

 

public class Solution {
    public long gridGame(int[][] grid) {
        long[] prefix = new long[grid[0].length];
        long[] suffix = new long[grid[0].length];
        prefix[0] = grid[0][0];
        suffix[grid[0].length-1] = grid[1][grid[0].length-1];
        for (int i = 1; i < grid[0].length; i++) {
            prefix[i] = prefix[i-1] + grid[0][i];
        }
        for (int i = grid[0].length-2; i >= 0; i--) {
            suffix[i] = suffix[i+1] + grid[1][i];
        }
        long robot2Max = Long.MAX_VALUE;
        for (int i = 0; i < grid[0].length; i++) {
            robot2Max =Math.min(robot2Max, Math.max(prefix[grid[0].length-1]-prefix[i],suffix[0]-suffix[i]));
        }

        return robot2Max;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        solution.gridGame(new int[][]{{1,3,1,15},{1,3,3,1}});
    }
}