누적합 응용(feat. 2차원 배열)

2차원 배열에 대한 구간합 문제가 나왔는데 내용이 기록하기 좋은 것 같아서 작성해보려고 한다.

누적합에 대한 내용보다는 문제를 살펴보면서 어떻게 누적합을 사용해서 풀었는지에 대해서 얘기하려고 한다.

누적합(Prefix Sum)에 관한 내용은 아래를 참고해 주세요.
누적합(Prefix Sum)

백준 11660번 구간 합 구하기 5

문제 내용을 간단히 얘기하자면 $ N \cdot N $ 크기의 표가 주어지고 $ (x1, y2) $부터 $ (x2, y2) $까지 합을 구하는 것이다.

ex) $ N = 4 $이고, 표가 아래와 같이 채워져 있는 경우. (2, 2)부터 (3, 4)까지 합을 구하면 $ 3+4+5+4+5+6 =  27 $이다.

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

 

이때 누적합을 어떻게 사용하는지 알아보려고 한다.

먼저 1차원 배열일 때 누적합을 생각해 보면 단순히 이전 값과 입력 값을 더하면서 채워 나가면 된다. 아래와 같은 배열이 만들어진다.

0

1

3

6

10

 

2차원일 때는 단순히 이전 값과 입력 값만 더하면서 채워 나가면 안 된다.

별표 좌표의 값은 빨간색 구역의 합을 구한 것에 해당한다. 근데 왜 "8"이라는 값이 들어갔는지 이해가 안 됐을 수도 있다.

더 자세히 처음부터 살펴보면 다음과 같다.

누적합은 값을 저장할 때 이전 값을 통해 저장하기 때문에 1번째 인덱스부터 시작하는데 0번째 배열을 같이 표시했다.

(1, 1)에 있는 1은 입력 값이다. (0, 0)부터 (1, 1)까지 합을 구하기 위해서 첫 번째 이미지 빨간색 구역과 두 번째 이미지 빨간색 구역을 더하고 1을 더해주면 된다. 이때 (0, 0)에 해당하는 부분은 중복이 발생한다. 그래서 (0, 0)의 값을 빼준다.

 

이를 식으로 표현하면 다음과 같다.

$$ arr[i][j] = arr[i][j - 1] + arr[i - 1][j] + 입력값(1) - arr[i - 1][j - 1] $$

$ arr[i][j - 1] $가 첫 번째 이미지에 해당하고 $ arr[i - 1][j] $가 두 번째 이미지에 해당한다. $ arr[i - 1][j - 1] $가 앞의 2개의 영역에 중복되기 때문에 빼는 영역이다.

그럼 이제 별표가 있던 좌표를 생각해 보면 쉽게 구해질 것이다.

$ arr[i][j - 1] = 3, arr[i - 1][j] = 3, arr[i - 1][j - 1] = 1 $로 $ 3(입력값) + 3 + 3 - 1 = 8 $가 나온다.

 

입력 값에 대한 누적합 배열을 만들면 다음과 같다.

그럼 이제 진짜 (2, 2)부터 (3, 4)까지 합을 구해보겠다.

별표가 있는 (3, 4)는 누적합이 (1, 1)부터 (3, 4)까지 합이다. 결국 우리가 구하려고 하는 영역의 값을 구하기 위해서는 두 번째 배열의 빨간색 영역에 해당하는 누적합 값 6(별표)을 빼주고 세 번째 배열의 빨간색 영역에 해당하는 누적합  값 10(별표)을 빼주고 겹치는 중복의 3번째 배열의 빨간색 영역 값 1(별표)을 더해주면 우리가 원하는 영역의 합을 구할 수 있다.

 

즉, 우리가 누적합 배열을 만들었을 때의 식을 반대로 해서 구할 수 있다.

$$ arr[x2][y2] - arr[x1 - 1][y2] - arr[x2][y1 - 1] + arr[x1 - 1][y1 - 1] $$

백준 11660 구간 합 구하기 5 구현(C++)

백준 11660 구간 합 구하기 5

 

문제의 범위는 $ N, M (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) $다.

일반적으로 구하면 $ 1024 \cdot 1024 \cdot 100,000 $으로 시간 초과가 발생한다.

누적합으로 다음의 시간복잡도로 구할 수 있다.

$$ O(N^2) $$

#include<bits/stdc++.h>
using namespace std;
#define FAST_IO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m, nx1, ny1, nx2, ny2, psum[1030][1030], a;
int main(){
    FAST_IO;
    cin >> n >> m;
    for(int i = 1; i <= n; ++i){
        for(int j= 1; j <= n; ++j){
            cin >> a;
            psum[i][j] = psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1] + a;
        }
    }
    for(int i = 0; i < m; ++i){
        cin >> nx1 >> ny1 >> nx2 >> ny2;
        cout << psum[nx2][ny2] - psum[nx1-1][ny2] - psum[nx2][ny1-1] + psum[nx1-1][ny1-1] << "\n";
    }
    return 0;
}

 

 

 

🔗 Reference

• 백준 11660 구간 합 구하기 5