[BOJ] 11660 : 구간 합 구하기 5 - travelbeeee

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

---

[ 알고리즘풀이 ]

1. 입력된 배열에서 각 Row 별로 sum 을 담고 있는 sumRow 배열을 정의합니다.

- sumRow[i][j] : i 행 0 ~ j 열까지의 합.

	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			sumRow[i][j] = map[i][j] + sumRow[i][j - 1];

O(N^2) 만에 sumRow 배열을 채울 수 있습니다.

2. input이 들어오면 sumRow 배열을 이용해서 O(N) 만에 답을 찾아낼 수 있습니다.

즉, input M개에 대해서 O(N * M) 만에 답을 찾아낼 수 있습니다.

(x1, y1) ~ (x2, y2)의 합을 구해달라고 했을 때, x1 ~ x2 행 별로

sumRow[ ][ y2 ] - sumRow[ ][ y1 - 1] 을 한다면 y1 ~ y2 열의 합을 쉽게 얻어낼 수 있습니다.

#include<iostream>

using namespace std;
int N, M, a, b, c, d, map[1025][1025] = {}, sumRow[1025][1025] = {};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			cin >> map[i][j];
	for (int i = 1; i <= N; i++)
		for (int j = 1; j <= N; j++)
			sumRow[i][j] = map[i][j] + sumRow[i][j - 1];
	for (int i = 0; i < M; i++) {
		int sum = 0;
		cin >> a >> b >> c >> d;
		for (int j = a; j <= c; j++)
			sum += sumRow[j][d] - sumRow[j][b - 1];
		cout << sum << '\n';
	}
	return 0;
}

---