[백준] 실버1 : (11659) 구간 합 구하기 5

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

11660번: 구간 합 구하기 5

 

2차원 부분 합 문제

먼저, 부분 합 배열을 만든다.

• 2차원 배열에서 각 1차원 배열(X)부터 부분 합을 구한다.
• 그 후, 다시 전체를 순회하며 이번에는 해당 좌표에 Y-1 값을 추가한다.

 

다음으로 시작 구간에서 끝 구간의 크기를 구하는 방법은 다음과 같다.

• 먼저, 끝 구간의 값 Answer을 저장한다.
• 끝 구간이자 결과값인 Answer은 전체 좌표를 시작으로 Answer의 좌표까지 모두 더한 값이다.
• 여기서, 시작 구간 ~ 끝 구간을 제외한 구간을 Answer에서 뺴주면 정답이 도출된다.

 

그림으로 설명하자면, 현재 초록 영역의 크기를 구해야 한다.

빨간 영역을 지워주면 구하고자하는 초록 영역만 남게 된다.

빨간 부분의 세로, 가로 영역을 지우면 둘의 합집합 부분을 두 번 빼게 된다.

이는 시작 구간(3, 3)에서 (0, 0)의 영역을 더해주면 된다.

 

#include <iostream>
#include <vector>
using namespace std;

int N, M;
vector<vector<int>> Numbers, Psum;

vector<vector<int>> PartialSum(const vector<vector<int>>& a)
{
	vector<vector<int>> Temp(a.size());
	for (int i = 0; i < N; ++i)
	{
		Temp[i].resize(a[i].size());
		Temp[i][0] = a[i][0];
	}

	// X축 합 구하기
	for (int i = 0; i < a.size(); ++i)
		for (int j = 1; j < a.size(); ++j)
			Temp[i][j] = Temp[i][j - 1] + a[i][j];

	// Y축 합 구하기
	for (int i = 1; i < a.size(); ++i)
		for (int j = 0; j < a.size(); ++j)
			Temp[i][j] += Temp[i - 1][j];

	return Temp;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	Numbers.resize(N);

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0, k; j < N; ++j)
		{
			cin >> k;
			Numbers[i].push_back(k);
		}
	}

	Psum = PartialSum(Numbers);

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

		int Answer = Psum[y2][x2];
		if (y1 > 0) Answer -= Psum[y1 - 1][x2];
		if (x1 > 0) Answer -= Psum[y2][x1 - 1];
		if (y1 > 0 && x1 > 0) Answer += Psum[y1 - 1][x1 - 1];
		cout << Answer << "\n";
	}
}