[백준/BOJ] 2167 2차원 배열의 합 (c++)

[백준/BOJ] 2167 2차원 배열의 합 (c++)

2167번: 2차원 배열의 합

2025.03.19 - [Competitive Programming] - 18. 구간 쿼리, 구간 합 (Range queries, Prefix sum, c++)

18. 구간 쿼리, 구간 합 (Range queries, Prefix sum, c++)

---

2차원 배열에서의 구간합을 구하는 문제입니다.

 

a[i][j] 를(1,1) 에서부터 (i, j) 까지의 사각형 범위의 합계라고 정의한다면,

 

a[i][j]는 a[i-1][j] 과 a[i][j-1]을 더하고 겹치는 구간인 a[i-1][j-1]에 (i,j)값을 더하는 것으로 계산할 수 있습니다.

 

이렇게 계산된 값을 이용한다면 특정 사각형 범위에 대한 합계를 구하는 것은 O(1) 시간복잡도로 수행됩니다.

 

미리 prefix sum을 구한 것과 비슷한 원리로, 우측 하단 모서리 까지의 전체 합에서 왼쪽,위쪽 모서리까지의 사각형을 빼고 겹치는 부분을 더하는 것으로 구할 수 있습니다. 

---

#include <bits/stdc++.h>
using namespace std;
#define REP(i, s, e) for (int i=s; i<e; i++)
int N, M, K, x, a1, a2, b1, b2;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    int a[301][301];
    memset(a, 0, sizeof a);
    REP(i, 1, N+1) {
        REP(j, 1, M+1) {
            cin >> x;
            a[i][j] = a[i-1][j]+a[i][j-1]-a[i-1][j-1]+x;
        }
    }
    cin >> K;
    REP(i, 0, K) {
        cin >> a1 >> a2 >> b1 >> b2;
        cout << (a[b1][b2]-a[b1][a2-1]-a[a1-1][b2]+a[a1-1][a2-1]) << "\n";
    }

    return 0;
}