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

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

11660번: 구간 합 구하기 5

풀이과정

1. 아래 표에서 \((0,0)\)부터 \((i, j)\)까지의 합은 다음 식으로 구할 수 있다.

$$ S(i, j) = A(i, j) + S(i, j - 1) + S(i - 1, j - 1) - S(i - 1, j - 1)$$

2. 아래 그림에서 초록색 칸을 모두 더하고 주황색 칸을 모두 뺀 값이라고 생각하면 된다.

3. \((r_1,c_1)\)부터 \((r_2,c_2)\)까지의 부분합은 다음과 같다.

$$\text{Partial Sum} = S(r_2,c_2) - S(r_1 - 1, c_2) - S(r_2, c_1 - 1) + S(r_1 - 1, c_1 - 1)$$

코드

#include <bits/stdc++.h>

using namespace std;

#define FAST_IO cin.tie(NULL); ios::sync_with_stdio(false);
#define FOR(i, N) for(int i = 0; i < N; ++i)
#define INF 987654321
#define EL "\n"

int main() {
#ifdef DEBUG
	freopen("input.txt", "r", stdin);
	//	freopen("output.txt", "w", stdout);
#endif
	FAST_IO;

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

	vector<vector<int>> table(N, vector<int>(N));
	FOR(r, N) FOR(c, N)
		cin >> table[r][c];

	vector<vector<int>> S(N, vector<int>(N));
	FOR(r, N) FOR(c, N) {
		S[r][c] = table[r][c];
		if (r > 0)
			S[r][c] += S[r - 1][c];
		if (c > 0)
			S[r][c] += S[r][c - 1];
		if (r > 0 && c > 0)
			S[r][c] -= S[r - 1][c - 1];
	}

	FOR(i, M) {
		int r1, c1, r2, c2;
		cin >> r1 >> c1 >> r2 >> c2;
		int partial_sum = S[r2 - 1][c2 - 1];
		if (r1 > 1)
			partial_sum -= S[r1 - 2][c2 - 1];
		if (c1 > 1)
			partial_sum -= S[r2 - 1][c1 - 2];
		if (r1 > 1 && c1 > 1)
			partial_sum += S[r1 - 2][c1 - 2];
		cout << partial_sum << EL;
	}

	return 0;
}

제출결과