누적 합

2차원 배열의 누적합을 구하는 방법을 알아보자.

핵심 포인트는 공통된 부분을 제거한다는 것!

 

원본 배열에 따른 누적합 배열은 위와 같다. (1,1)을 기준으로 특정 좌표까지의 합을 저장한 것이 누적합 배열이다.

 

 

(2,2)의 누적합을 구하는 방법이다.

 

---

 

구간합을 구할때는 누적합 배열을 이용한다. 누적합이 (1,1)을 기준으로 구해졌으므로, 해당하지 않는 부분을 빼 준 후, 공통 부분의 누적합을 다시 더해주면 된다.(공통된 부분이라 값이 중복으로 빠졌으므로)

 

 

누적합과 구간합을 코드로 구현해보자. 아래의 코드를 2중 for문으로 (1,1)부터 마지막 좌표까지 돌면서 수행하면 된다.

 

* 누적합 구하기

sumArr[i][j] = arr[i][j] + sumArr[i - 1][j] + sumArr[i][j - 1] - sumArr[i - 1][j - 1];
// sumArr = 누적합 배열, arr = 기본 배열

 

* 구간합 구하기

int result = sumArr[c][d] + sumArr[a - 1][b - 1] - sumArr[c][b - 1] - sumArr[a - 1][d];
// (a,b) 부터 (c,d) 까지의 구간의 값들 합

 

아래 2 문제는 2차원 배열의 누적합과 구간합 구해서 풀이하는 문제이다.

 

관련 문제 1 : 백준 16507 - 어두운 건 무서워

https://www.acmicpc.net/problem/16507

16507번: 어두운 건 무서워

 

코드

#include <iostream>

using namespace std;

int arr[1001][1001];
int sumArr[1001][1001];

int main() {
    int R, C, Q;
    cin >> R >> C >> Q;
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            cin >> arr[i][j];
        }
    }

    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            sumArr[i][j] = arr[i][j] + sumArr[i - 1][j] + sumArr[i][j - 1] - sumArr[i - 1][j - 1];
        }
    }

    for (int i = 0; i < Q; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        int sumVal = sumArr[c][d] + sumArr[a - 1][b - 1] - sumArr[c][b - 1] - sumArr[a - 1][d];
        int tmp = (c - a + 1) * (d - b + 1);
        cout << sumVal / tmp << '\n';
    }
}

 

관련 문제 2 : 백준 15724 - 주지수

https://www.acmicpc.net/problem/15724

15724번: 주지수

 

코드

#include <iostream>

using namespace std;

int arr[1025][1025];
int sum[1025][1025];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N, M, K;
    cin >> N >> M;

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= M; j++) { //가로로 더하고
            cin >> arr[i][j];
            sum[i][j] = arr[i][j] + sum[i][j - 1];
        }
        for (int j = 1; j <= M; j++) { //누적시키기
            sum[i][j] += sum[i - 1][j];
        }
    }

    cin >> K;
    for (int i = 0; i < K; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;

        cout << sum[c][d] - sum[a - 1][d] - sum[c][b - 1] + sum[a - 1][b - 1] << '\n';
    }
}