[C++] 백준 11660번: 구간 합 구하기 5

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

11660번: 구간 합 구하기 5

최초풀이

시간초과 에러가 많이 발생하는 문제입니다.

DP 알고리즘을 잘활용하고 빠른 입출력 처리도 해주어야 합니다.

#include <iostream>

using namespace std;

int dp[1025][1025];

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++) {
			cin >> dp[i][j];
			dp[i][j] = dp[i-1][j]+dp[i][j-1] - dp[i-1][j-1] +dp[i][j];
		}
	}

	while (M--) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;

		cout << dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1] << '\n';
	}

	return 0;
}