백준 11660번 : 구간 합 구하기 5

문제 링크 : www.acmicpc.net/problem/11660

내 풀이(2021.1.29.) :

#include <iostream>

using namespace std;

int dp[1025][1025]; // [x][y]

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

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

	for (int i = 2; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			dp[i][j] += dp[i - 1][j];
		}
	}

	for (int i = 0; i < M; i++) {
		int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
		int sum = 0;
		sum += dp[x2][y2];
		if (y1 != 1) sum -= dp[x2][y1 - 1];
		if (x1 != 1) sum -= dp[x1 - 1][y2]; 
		if (x1 != 1 && y1 != 1)	sum += dp[x1 - 1][y1 - 1];
		cout << sum << '\n';
	}

	return 0;
}

매번 2중 for문으로 합을 구하면 시간 초과가 난다.

좌표별로 누적 합을 미리 구해놓은 뒤, 누적 합들의 덧셈/뺄셈 연산을 통해 빠르게 구해야 한다.