백준 2167 2차원 배열의 합 c++ (누적 합)

문제 출처 : https://www.acmicpc.net/problem/2167

2167번: 2차원 배열의 합

문제

2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다.

입력

첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(i ≤ x, j ≤ y).

출력

K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 231-1보다 작거나 같다.

알고리즘 분류

• 구현
• 누적 합

풀이

2차원 누적 합 기본 문제이다.

2차원 그래프에서 누적 합(2,1)은 

1	0	0	1
0	0	1	1
1	2	1	1
2	0	3	0

1,1 + 1,2 + 1,3+ 1,4 + 2,1이 아니라,

1	0	0	1
0	0	1	1
1	2	1	1
2	0	3	0

1,1 + 2,1이다.

 

아래의 그래프에서 누적 합을 구해보자.

1	0	0	1
0	0	1	1
1	2	1	1
2	0	3	0

<graph>

 

 

 

1	1	1	2
0	0	1	2
1	3	4	5
2	2	5	5

<누적합 (Row)>

우선 Row방향으로 모두 누적 합을 구한다.

 

 

 

1	1	1	2
1	1	2	4
2	4	6	9
4	6	11	14

<누적합 (Row*Column)>

이후 Column방향으로 모두 누적 합을 구한다.

위의 그래프가 누적합이 완성된 모습이다.

 

 

11	12	13	14
21	22	23	24
31	32	33	34
41	42	43	44

그래프에서 (2,2)~(4,4)구간의 합은 빨간색 부분이다.

 

이를 구하는 방법은

11	12	13	14
21	22	23	24
31	32	33	34
41	42	43	44

전체 그래프의 합에서 노란색 부분과, 연두색 부분을 빼주고, 두 부분이 겹치는 분홍색 부분은 두 번 빼졌으니, 한 번 더해주면 된다.

이를 식으로 하면 다음과 같다.

//pSum =누적합

sum(2,2~4,4) = pSum[4][4] -pSum[4][1] -pSum[1][4] + pSum[1][1]이다.

 

위의 방법으로 그래프 전체의 누적합을 만들려면 2중for문(row방향 누적합) + 2중 for문(col방향 누적합)이 필요한데,

아래의 코드를 보면 위의 과정을 한 번의 2중for문(row방향 누적합 + col방향 누적합)으로 만들 수 있다.

 

 

코드

#include <iostream>

#define MAX 301
using namespace std;

long long pSum[MAX][MAX];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n,m;
	cin >> n>>m;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> pSum[i][j];
			pSum[i][j] += pSum[i][j-1] +pSum[i-1][j]-pSum[i-1][j-1];
		}
	}
	int k;
	cin >> k;
	
	for (int i = 0; i < k; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		cout << pSum[c][d] - pSum[a - 1][d] - pSum[c][b - 1] + pSum[a - 1][b - 1]<<'\n';
	}

	return 0;
}