[백준/BOJ] 15724 주지수

문제 : 15724 주지수

15724번: 주지수

직사각형의 범위가 주어질 때 그 안에 사는 사람 수의 합을 출력하는 문제이다.

배열의 길이가 N, 주어지는 범위의 개수가 M일 때 그냥 구하게 되면

O(N^2*M)으로 시간 초과이므로 누적합 배열을 이용해

시간을 O(N^2+M)으로 줄여서 구하면 된다.

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll N, M, T, arr[1050][1050];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    for (int i=1;i<=N;i++){
        for (int j=1;j<=M;j++){
            ll a;
            cin >> a;
            arr[i][j]=a+arr[i-1][j]+arr[i][j-1]-arr[i-1][j-1];
        }
    }
    cin >> T;
    while (T--){
        ll x1, x2, y1, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << arr[x2][y2]-arr[x1-1][y2]-arr[x2][y1-1]+arr[x1-1][y1-1] << "\n";
    }
    return 0;
}