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

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

11660번: 구간 합 구하기 5

백준 11660번 구간 합 구하기 5를 풀었다.

 

2차원 배열에서 구간 합을 구하는 문제다. 행 별로 누적 합을 구한 뒤에 각 행마다 구간 합 연산을 해주면 된다.

	1	2	3	4
1	1	2	3	4
2	2	3	4	5
3	3	4	5	6
4	4	5	6	7

처음 입력 받은 배열이다. 0번째 index는 생략했다.

 

행 별로 누적 합 연산을 해보면 아래 표처럼 바뀐다.

	1	2	3	4
1	1	3	6	10
2	2	5	9	14
3	3	7	12	18
4	4	9	15	22

문제 예제처럼 (2, 2)에서 (3, 4)를 구하려면 빨간 배경의 누적 합을 행 별로 구하면 된다.

2행의 누적 합 값은 (2, 4)의 값인 14에서 (2, 1)의 값인 2를 뺀 12이다.

3행의 누적 합 값은 (3, 4)의 값인 18에서 (3, 1)의 값인 3을 뺀 15이다.

이 둘을 합친 것이 정답이 된다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;

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

int main() {
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf_s("%d", &arr[i][j]);
		}
	}

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

	while (M--) {
		int x1, y1, x2, y2;
		int sum = 0;
		scanf_s("%d %d %d %d", &x1, &y1, &x2, &y2);
		for (int i = 0; i < x2 - x1 + 1; i++) {
			sum += arr[x1 + i][y2] - arr[x1 + i][y1 - 1];
		}
		printf_s("%d\n", sum);
	}

	return 0;
}