[LeetCode] 598. Range Addition II

문제 출처: https://leetcode.com/problems/range-addition-ii/

Range Addition II - LeetCode

---

문제

0으로 초기화된 $m \times n$ 크기의 행렬 $M$과 일련의 작업이 기록되어 있는 배열 $ops$가 주어진다. $ops[i] = [a_i, b_i]$는 모든 $0 \le x < a_i$ 와 $0 \le y < b_i$에 대해 $M[x][y]$를 증가시키는 작업을 의미한다.

 

모든 작업을 수행한 후 행렬 내에서 가장 큰 정수의 개수를 반환하라.

예제

Input: m = 3, n = 3, ops = [[2,2],[3,3]]
Output: 4

Explanation: The maximum integer in M is 2, and there are four of it in M. So return 4.

Input: m = 3, n = 3, ops = [[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3]]
Output: 4

Input: m = 3, n = 3, ops = []
Output: 9

---

풀이

문제를 다음과 같이 생각할 수 있다.

 

m x n 크기의 하얀 도화지가 있다. 그 위에 ops[i][0] x ops[i][1] 크기의 셀로판지를 도화지 왼쪽 상단 모서리에 맞춰 겹겹이 쌓는다. 이때 가장 진한 색을 갖는 부분의 크기는 얼마인가.

ops[i][0] 중에서 가장 작은 값과 ops[i][1] 중에서 가장 작은 값을 구하는 것으로 그 답을 구할 수 있다.

var maxCount = function(m, n, ops) {
    let minX = m;
    let minY = n;
    
    for (let [x, y] of ops) {
        minX = Math.min(minX, x);
        minY = Math.min(minY, y);
    }
    
    return minX * minY
};

 

Github: 598.js

GitHub - opwe37/Algorithm-Study