백준 11660 구간 합 구하기 5 C++

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

11660번: 구간 합 구하기 5

x1, y1 부터 x2, y2 까지의 합을 구하는 문제입니다.
얼핏보면 n이 최대 1024라 그냥 다 더하면 될 거 같지만 100000번 수행해야 하므로 브루트포스로는 안 됩니다. 

dp를 이용해 1,1부터 x,y까지의 합을 먼저 구하면 다음과 같습니다.
dp[i][j] = num + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
(num : 해당 위치 숫자)

그리고 x1, y1 ~ x2, y2까지의 합은 결국 사각형을 그려보면 1,1 ~ x2, y2까지 합에서 1,1 ~ x2, y1-1까지 합 + 1,1 ~ x1-1, y2 까지 합 - 1,1 ~ x1-1, y1-1 까지 합 임을 알 수 있습니다.

코드는 다음과 같습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

// dp[i][j] = num + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
// x1, y1 ~ x2, y2까지 합
// dp[x2][y2] - (dp[x2][y1-1] + dp[x1-1][y2] - dp[x1-1][y1-1])

int n, m;
int map[1025][1025];
int dp[1025][1025]; // [1][1] ~ [x][y] 까지 합

void init()
{
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];
		}
	}
}

void getDP()
{
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			dp[i][j] = map[i][j];
			dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1];
		}
	}
}

int getResult(int x1, int y1, int x2, int y2)
{
	return dp[x2][y2] - (dp[x2][y1 - 1] + dp[x1 - 1][y2] - dp[x1 - 1][y1 - 1]);
}

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

	init();
	getDP();
	while (m--) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		cout << getResult(x1, y1, x2, y2) << '\n';
	}
}