[백준 11660번] 구간 합 구하기 5 (C++)

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

11660번: 구간 합 구하기 5

---

구간 합 구하기 5 문제는 행 누적 배열을 이용하여 해결할 수 있습니다. 계산의 편의성을 위해 가장 왼쪽에는 0을 넣어주었습니다.

// 입력 배열
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

// 누적 배열
0 1 3 6 10 
0 2 5 9 14 
0 3 7 12 18 
0 4 9 15 22

(x1, y1)부터 (x1, y2)까지의 합은 accu[x1][y2] - accu[x1][y1 - 1]으로 계산할 수 있습니다. (단, accu는 행 누적 배열)

 

아래는 전체 코드입니다.

#include <bits/stdc++.h>
using namespace std;

int accu[1024][1025];   // 누적 배열

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, m; cin >> n >> m;
    for(int i = 0; i < n; i++){
        for(int j = 1; j <= n; j++){
            int t, pre; cin >> t;
            if(j == 0) pre = 0; // 가장 왼쪽 원소는 0으로 채움
            else {
                pre = accu[i][j - 1];
                accu[i][j] = t + pre;
            }
        }
    }

    for(int i = 0; i < m; i++){
        int x1, y1, x2, y2, t = 0;
        cin >> x1 >> y1 >> x2 >> y2;

        for(int i = x1 - 1; i < x2; i++)
            t += accu[i][y2] - accu[i][y1 - 1]; // 우측 누적 - 좌측 누적
        cout << t << "\n";
    }
}