[LeetCode] 2017. Grid Game

https://leetcode.com/problems/grid-game/description/

leetcode - Grid Game

문제 유형: 부분합, 구간합, 그리디

문제 난이도: 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.

 

2D배열이 2 x n의 꼴로 주어집니다.

두 로봇은 (0, 0)에서 시작해서, (1, n-1)에서 멈춥니다. 오른쪽 또는 아래로만 이동가능합니다.

먼저 가는 로봇이 셀의 숫자만큼 점수를 얻고 셀을 0으로 만듭니다.

그 다음에 가는 로봇도 그렇게 움직입니다.

각 로봇이 최대한 많은 점수를 얻기 위해 움직입니다.

로봇 2가 얻는 최대의 점수를 구하시오.

 

풀이

 

빨간색 경로를 첫 번째 로봇이 지난 경로라 하자. 두 번째 로봇은 파란색으로 칠해진 두 가지 영역 중 하나를 먹어야 하고, 그 둘 중 최대가 두 번째 로봇이 얻는 최대 점수이다.

각 행별로 prefix Sum을 구해서, 더 큰쪽을 택한다. 그 뒤, 첫 번째 로봇이 최대를 먼저 취한다고 가정했으니, 각 경우들 중에서 가장 작은 값을 택해야 한다. 첫 번째 로봇이 최대로 간 경로의 의미는, 두 번째 경로의 최선의 경우의 수들중 최소값이라는 것이다.

 

즉, 그림에서 파란색 구간합들을 계산해서 더 큰쪽을 고르고, 그 값들의 최소값을 구하면 된다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-loops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    long long gridGame(vector<vector<int>>& grid) {
        int n = grid[0].size();

        vector<long long> prefixSum0(n+1, 0);
        vector<long long> prefixSum1(n+1, 0);

        for(int i = 1; i <= n; ++i) {
            prefixSum0[i] += prefixSum0[i-1] + grid[0][i-1];
            prefixSum1[i] += prefixSum1[i-1] + grid[1][i-1];
        }

        long long ans = LLONG_MAX;
        for(int i = 0; i < n; ++i) {
            long long bScore = max(prefixSum0[n] - prefixSum0[i+1], prefixSum1[i]);
            ans = min(ans, bScore);
        }
        
        return ans;
    }
};