11660_구간 합 구하기 5

▶실버1

 

풀이

누적 합 이용.

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

=> 배열 표

	0	1	2	3	4
0	0	0	0	0	0
1	0	1	3	6	10
2	0	3	8	15	24
3	0	6	15	27	42
4	0	10	24	42	64

=> 누적 합 표

ex) (2, 2) ~ (3, 4) 의 구간 합

이는 8 + 15 + 24 + 15 + 27 + 42 와 같은데, 누적합을 이용하면

sum[3][4] - sum[3][1] - sum[1][4] + sum[1][1] 임을 알 수 있다.

 

이를 통하여 (x1, y1) ~ (x2, y2)의 구간 합의 점화식은 sum[x2][y2] - sum[x2][y1 -1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1] 이다.

또, 주의할 점은 x1 == 1 || y1 == 1일 경우에 범위가 벗어나므로 x = 0 || y = 0의 인덱스를 가지는 배열을 0으로 채워준다.(가장 윗 줄과 가장 왼쪽 줄)

코드

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int sum[1030][1030];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n, m;
	cin >> n >> m;
	for (int i = 0; i <= n; i++) {
		for (int j = 0; j <= n; j++) {
        	//가장자리 0으로 채우기
			if (i == 0 || j == 0) {
				sum[i][j] = 0;
				continue;
			}

			int num;
			cin >> num;

			
			if (i > 1 && j > 1) {
				sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + num;
			}
			else if (i == 1 && j > 1) {
				sum[i][j] = sum[i][j - 1] + num;
			}
			else if (i > 1 && j == 1) {
				sum[i][j] = sum[i - 1][j] + num;
			}
			else {
				sum[i][j] = num;
			}
			
		}
	}


	for (int i = 0; i < m; i++) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		int ans = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
		cout << ans << "\n";
	}
}