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

문제

11660번: 구간 합 구하기 5

N X N 의 2차원 배열이 주어지고 (x1, y1) ~ (x2, y2) 까지의 합을 구하는 문제입니다.

예를 들어 n = 4 이고 (2, 2) ~ (3, 4) 구간의 합을 구하고 싶으면

1 2 3 4

2 3 4 5

3 4 5 6

4 5 6 7

빨간색 부분의 합을 구하면 됩니다.

 

prefix sum 형태로 해결하였습니다

psum[x][y] = (1, 1) 부터 (x, y)의 합으로 정의 하였습니다.

예를 들어 psum[2][2]를 구하고 싶으면 

psum[2][2] = psum[1][2] + psum[2][1] - psum[1][1] + arr[2][2] 가 됩니다.

따라서 점화식을 세우면 psum[x][y] = psum[x-1][y] + psum[x][y-1] - psum[x-1][y-1] + arr[x][y] 가 됩니다.

for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            psum[i][j] = psum[i][j-1]+psum[i-1][j]-psum[i-1][j-1]+arr[i][j];
        }
    }

이제 (2, 2) ~ (3, 4)를 구하려면 다음과 같습니다.

노란색 부분을 구하기 위해서는 

(2, 2) ~ (3, 4) = psum[3][4] - psum[1][4] - psum[3][1] + psum[1][1] 가 됩니다.

따라서 점화식 (x1, y1) ~ (x2, y2) = psum[x2][y2] - psum[x1 - 1][y2] - psum[x2][y1 - 1] + psum[x1 - 1][y1 - 1]

int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cout << psum[x2][y2] - psum[x1 - 1][y2] - psum[x2][y1 - 1] + psum[x1 - 1][y1 - 1] << '\n';

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int arr[1025][1025];
int psum[1025][1025];
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n, m;
    cin >> n>>m;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++) 
            cin >> arr[i][j];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            psum[i][j] = psum[i][j-1]+psum[i-1][j]-psum[i-1][j-1]+arr[i][j];
        }
    }
    
    
    while (m--) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        cout << psum[x2][y2] - psum[x1 - 1][y2] - psum[x2][y1 - 1] + psum[x1 - 1][y1 - 1] << '\n';
    }
        
    
 
    return 0;
}