https://school.programmers.co.kr/learn/courses/30/lessons/92344
N x M의 필드에 각 건물의 내구도가 존재한다.
인풋으로 들어오는 skill 배열의 각 요소는 (r1, c1)에서 (r2, c2)까지 직사각형 범위의 내구도를 특정 수만큼 깎거나 회복시킨다.
모든 skill을 처리한 후 내구도가 0 이상인 건물의 수를 찾는 문제이다.
필드의 크기가 최대 1000 x 1000이고 skill 배열의 크기가 250,000까지이다.
이 문제도 직접 풀지는 못했지만, 알려진 풀이에서 얻어갈 것이 있는 문제였다.
일차원 배열에서의 누적합은 단순히 한 번 지나가며 누적합을 저장하고 갱신하는 것이었다.
하지만 위 문제는 이차원 배열인 데다가 특정 좌표에서 다른 좌표까지의 직사각형 범위의 누적합을 구해야 한다.
이차원 배열에서 직사각형 범위의 누적합을 구하는 방법을 알아보자.
위 직사각형 필드에서 (0, 0)에서 (3, 3)까지 5만큼을 더해보자.
누적합을 통해 범위에 값을 누적하는 방법은 위와 같다.
(0, 0)에 더할 숫자 x, (0, 4)에 -x, (4, 0)에 -x, (4, 4)에 x를 더하면 된다.
단순히 네 꼭짓점에 위 방식대로 숫자를 더하는 것이 누적이라 할 수 있다.
모든 숫자를 누적했다 치고 위 배열을 합해보자.
합하는 과정은 일차원 배열의 누적합을 구하듯, 이차원 배열의 각 행을 먼저 쭉 더하며 누적합을 입력한다.
이후 각 열을 쭉 더하며 누적합을 입력한다.
그럼 처음에 우리가 원하던 (0, 0)에서 (3, 3)까지 5만큼 더한 상태가 된다.
이런 식으로 모든 skill에 대해 네 꼭짓점 좌표에 수를 더하며 누적하고, 모든 skill을 누적했으면 이차원 배열을 가로로 한번, 세로로 한번 누적하며 최종 완성된 필드를 구하면 된다.
의도한 대로 동작하는 지 3개의 케이스를 넣어 다시 확인해 보자.
- skill(1, 0, 0, 3, 3, 4) -> (0, 0) ~ (3, 3)의 범위를 -4
- skill(2, 1, 1, 2, 3, 3) -> (1, 1) ~ (2, 3)의 범위를 +3
- skill(1, 2, 2, 3, 3, 2) -> (2, 2) ~ (3, 3)의 범위를 -2
1번은 (0, 0)에 -4, (0, 4)에 +4, (4, 0)에 +4, (4, 4)에 -4
2번은 (1, 1)에 +3, (1, 4)에 -3, (3, 1)에 -3, (3, 4)에 +3
3번은 (2, 2)에 -2, (2, 4)에 +2, (4, 2)에 +2, (4, 4)에 -2
위 방법대로 누적한 결과는 아래와 같다.
각 skill을 처리하는 시간은, 4 좌표에 대입이므로 이다.
그리고 먼저 가로로 누적합을 구하며 대입한다.
그리고 다시 세로로 누적합을 구하며 대입한다.
그러면 (0, 0)부터 (3, 3)까지의 파란색 범위가 각 skill을 처리한 누적합이 된다.
그러면 위 필드를 순회하며, 최초의 board 요소의 값과 누적합을 더해 0 이상이면 answer 카운트를 추가하면 된다.
이런 방법이 있었구나.. 하며 배워간다.
