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

문제

풀이

2차원 배열의 누적 합을 구하는 문제다.

입력을 받으면서 누적 합을 만들었고, i 또는 j의 인덱스가 0인 곳엔 0을 채워 넣었다.

큰 네모(arr[x2][y2]에서 가장자리에 해당하는 두 네모(arr[x2][y1 - 1], arr[x1 - 1][y2])를 빼주고,
작은 네모(arr[x1 - 1][y1 - 1]는 두번 빠졌기에 한번 더해줬다.

코드

#include <iostream>
#include <vector>

using namespace std;

int N, M;
int arr[1025][1025];

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

	// 표의 크기 N, 합을 구하는 횟수 M
	cin >> N >> M;

	// 입력 & 누적 합 구하기
	for (int i = 1; i < N + 1; i++) {
		for (int j = 1; j < N + 1; j++) {
			cin >> arr[i][j];
			arr[i][j] += arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1];
		}
	}

	// 출력
	int x1, y1, x2, y2;
	for (int i = 0; i < M; i++) {
		cin >> x1 >> y1 >> x2 >> y2;
		cout << arr[x2][y2] + arr[x1 - 1][y1 - 1] - arr[x2][y1 - 1] - arr[x1 - 1][y2] << "\n";
	}

	return 0;
}