[백준/BOJ] 백준 11660번 : 구간 합 구하기 5

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

11660번: 구간 합 구하기 5

 

2차원 누적합을 이용해서 문제를 해결했다.

 

코드

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

int n, m;

int board[1030][1030];
int psum[1030][1030];

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

	cin >> n >> m;

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			int input;
			cin >> input;

			board[i][j] = input;
		}
	}

	//2차원 누적합 구하기
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			psum[i][j] = psum[i][j - 1] + psum[i - 1][j] - psum[i - 1][j - 1] + board[i][j];
		}
	}

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

		cout << psum[x2][y2] - psum[x2][y1 - 1] - psum[x1 - 1][y2] + psum[x1 - 1][y1 - 1] << "\n";
	}

	return 0;
}