백준 - 11660번 : 구간 합 구하기 5 (C++)

풀이 방법 : 누적 합

각 행의 각 인덱스까지의 누적 합을 미리 구해놓고 입력이 주어지면 해당 인덱스에서 이전 인덱스의 누적 합을 빼주면 해당 구간 합이 구해진다. 이를 열 별로 반복하면 된다.

#include <iostream>

using namespace std;

int Sum[1025][1025] = {};

int main()
{
	cin.tie(nullptr);
	cout.tie(nullptr);
	ios::sync_with_stdio(false);

	int N, M;

	cin >> N >> M;

	for (int i = 1; i <= N; ++i)
	{
		for (int j = 1; j <= N; ++j)
		{
			int Num;
			cin >> Num;
			Sum[j][i] = Sum[j][i - 1] + Num;
		}
	}

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

		int Answer = 0;

		for (int j = y1; j <= y2; ++j)
		{
			Answer += Sum[j][x2] - Sum[j][x1 - 1];
		}

		cout << Answer << '\n';
	}

}