백준11660 - 구간 합 구하기 5

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

11660번: 구간 합 구하기 5

dp를 이용하여 풀었다. 우선 (1, 1) ~ (n, m)까지의 합을 구하였다. dp를 구할 때는 다음과 같이 네 구역으로 나누었다.

 

각 칸은 (1, 1) ~ (n, m)까지의 합을 더하여 저장한 것이다. 내가 구하고자 하는 칸에 값을 구하는 방법은 바로 위, 바로 옆의 값을 더한 뒤 중복된 값을 빼주면 된다.

 

 

이렇게 구한 결과에서 (a, b) ~ (c, d)까지의 합은 다음과 같이 구하면 된다.

D가 문제에서 구하려는 면적의 합이다.

 

#include <iostream>
#define MAX 1025
using namespace std;

int N, M;
int a, b, c, d;
unsigned long long int mat[MAX][MAX] = { 0, };
unsigned long long int dp[MAX][MAX] = { 0, };

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

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> mat[i][j];
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + mat[i][j] - dp[i - 1][j - 1];
		}
	}

	for (int i = 0; i < M; i++) {
		cin >> a >> b >> c >> d;
		cout << dp[c][d] - dp[c][b - 1] - dp[a - 1][d] + dp[a - 1][b - 1] << '\n';
	}
}