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

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

11660번: 구간 합 구하기 5

 

#include <stdio.h>
using namespace std;

int arr[1025][1025];

int main() {
	int n, m;
	scanf("%d %d", &n, &m);
	
	int num;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= n; j++){
			scanf("%d", &num);
			arr[i][j] = arr[i - 1][j] + arr[i][j - 1] + num - arr[i - 1][j - 1];
		}
	}
	
	int a, b, c, d;
	for(int i = 1; i <= m; i++){
		scanf("%d %d %d %d", &a, &b, &c, &d);
        printf("%d\n", arr[c][d] - arr[a - 1][d] - arr[c][b - 1] + arr[a - 1][b - 1]);
	}
	return 0;
}

 

 

각 arr[i][j]에 (0, 0)부터 (i, j)까지의 누적합을 저장한다.

 

(x1, y1), (x2, y2)의 값이 들어오면, 큰 정사각형에서 직사각형 2개를 빼준 뒤, 중첩된 작은 정사각형을 더해주면 (x1, y1) ~ (x2, y2)이 누적합을 구할 수 있다.