백준 11660번: 구간 합 구하기 5

[문제 링크]

11660번: 구간 합 구하기 5

---

M이 100,000으로 매우 크기 때문에 행을 입력 받을 때 미리 각 행의 누적합을 구해놓고 이를 참조하는 방식으로 구현하였다.

 

(2,2) ~ (3,4) 의 구간합을 구해보자면,

(2,2) ~ (2,4) 까지의 합 + (3,2) ~ (3,4) 까지의 합이 된다.

 

(2,2) ~ (2,4) 까지의 합은 미리 구해놨던 (2,1) ~ (2,4) 까지의 누적합에 (2,1) ~ (2,1) 까지의 누적합을 빼준 것과 같다는 것을 알 수 있다.

(3,2) ~ (3,4) 까지의 합도 마찬가지로 (3,1) ~ (3,4) 까지의 누적합에 (3,1) ~ (3,1) 까지의 누적합을 빼준 것과 같다.

---

#include <iostream>
using namespace std;

int memo[1025][1025];

int sum(int y1, int x1, int y2, int x2) {
	int result = 0;
	for (int y = y1; y <= y2; y++) {
		if (x1 == 1)
			result += memo[y][x2];
		else
			result += memo[y][x2] - memo[y][x1-1];
	}

	return result;
}

int main(void) {
	cin.tie(0);
	ios_base::sync_with_stdio(0);

	int N, M;
	cin >> N >> M;

	for (int y = 1; y <= N; y++) {
		for (int x = 1; x <= N; x++) {
			int num;
			cin >> num;

			if (x == 1)
				memo[y][x] = num;
			else
				memo[y][x] = memo[y][x - 1] + num;
		}
	}

	for (int i = 0; i < M; i++) {
		int x1, y1, x2, y2;
		cin >> y1 >> x1 >> y2 >> x2;

		cout << sum(y1, x1, y2, x2) << '\n';
	}

	return 0;
}