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

 

1) 문제설명

백준 Online Judge 11660번 구간 합 구하기 5

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

11660번: 구간 합 구하기 5

 

 

2) 아이디어

표를 그리면서 생각하였다.

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

입력받은 배열(표)에서 먼저 누적합을 구한다. 

sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + arr[i][j] - sum[i - 1][j - 1]; // 누적합

1	3	6	10
3	8	15	24
6	15	27	42
10	24	42	64

이후 좌표 x1, x2, y1, y2를 입력받은 후 우리가 구해야 하는 누적 합의 값을 생각해 본다면

1	2	3	4
2	3	4	5
3	4	5	6
4	5	6	7

3 + 4 + 5 + 4 + 5 + 6 = 27이다.

그런데 이 값은  sum(3,4) = 42에서 sum(1,4) = 10 , sum(3,1) = 6을 빼고 sum(1,1) = 1을 더한 값이다.

1	3	6	10
3	8	15	24
6	15	27	42
10	24	42	64

이를 토대로 점화식을 세운다면

result = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];

 

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;
int arr[1025][1025];
int sum[1025][1025];


int main() {
	int n, m;
	int x1, x2, y1, y2;
	int result;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%d", &arr[i][j]);
			sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + arr[i][j] - sum[i - 1][j - 1]; // 누적합
			
		}
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		result = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
		printf("%d\n", result);
	}
}