[백준] 11660번 - 구간 합 구하기 5

백준 온라인 저지의 11660번 구간 합 구하기 5 문제입니다.

[링크] https://www.acmicpc.net/problem/11660

문제 조건과 설명

N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오.

여기서 (2,2)부터 (3,4) 까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4,4)부터 (4,4)까지 합을 구하면 7이다.

Input

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000)

둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다.

다음 M개의 줄에 네 개의 정수 x1, y1, x2, y2 가 주어진다.

(x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. (여기서 x1, y1은 x1행, y1열을 의미한다. )

표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

Output

총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.

생각한 아이디어

구간 합 구하기 4의 2차원 배열 버전이라고 생각하면 될 것 같습니다.

먼저 구간합을 쭉 구해 놓습니다. 구하는 방법은 아래 사진을 참고하시면 됩니다.

주어진 표의 값들이 위와 같다고 가정해 보겠습니다.

왼쪽 표에 색칠된 모든 구역의 합은 1+2+3+2+3+4+3+4+5+4+5+6 = 42입니다.

즉, (1,1) 부터 (4,3) 까지의 구간을 나타낸 것인데,

오른쪽 표에는 그 구간합의 값을 저장합니다. 즉, 오른쪽 표의 (4,3)에는 (1,1)부터 (4,3)까지의 구간합이 들어갑니다.

다른 예시를 들어보겠습니다. 왼쪽 표는 (1,1)부터 (2,3)까지의 구간을 나타낸 것입니다.

이 구간의 합이, 오른쪽 표의 (2,3)에 들어갑니다.

이런 식으로 오른쪽 구간합 표를 미리 만들어 두어야 합니다.

그러면 오른쪽 표에 값을 채우는 방식에 대해 알아보겠습니다.

왼쪽 (1,1)~(2,2) 구간의 합을 구해서 오른쪽 표 (2,2)에 집어넣어야 하는 상황입니다.

오른쪽 표의 (1,2) 와 (2,1)을 더할 경우 합이 6 인데, (1,1)이 중복됩니다.

따라서 (1,1) 을 빼 줍니다. 지금까지의 구간합은 5 입니다.

여기에 원래 표의 (2,2) 값을 더해주면 끝납니다.

즉, 오른쪽 구간합 표의 (2,2) 에는 최종적으로 8이 들어가게 됩니다.

이는, (1,1)~(2,2) 까지 더한 합을 의미합니다.

즉, 오른쪽 표의 ( i, j ) 값은 원래 표의 (1,1)~( i, j ) 까지의 숫자 합을 의미하게 됩니다.

이것을 일반화하면 다음과 같습니다.

1
2
3
4
5
6

for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
		cin >> num;
		p_sum[i + 1][j + 1] = p_sum[i][j + 1] + p_sum[i + 1][j] - p_sum[i][j] + num;
	}
}

num 은 원래 표의 값을 말하고, p_sum(i+1)(j+1) 은 오른쪽 구간합 표의 값을 구하는 식입니다.

위 그림의 과정과, 소스코드의 덧셈 식이 동일함을 알 수 있습니다.

p_sum(i + 1 , j + 1) = p_sum(2,2) 의 값은 p_sum(1,2) + p_sum(2,1) - p_sum(1,1) + num 값이 됩니다.

이렇게 구간합 표를 만들어 두면, 답을 구할 차례만 남았습니다.

(내용 정정) 위 그림의 설명에서, (1,1)~(2,2) 부분합이 아니라 (1,1)~(3,2) 부분합이 맞습니다.

(2,3)~(3,4) 의 구간합을 구해야 한다고 가정해 보겠습니다.

왼쪽 표는 (1,1)~(3,4) 까지의 부분합에서 (1,1)~(1,4)의 부분합과 (1,1)~(3,2)의 부분합을 빼고,

두번 빼진 진하게 색칠된 영역의 합, 즉 (1,1)~(1,2)의 부분합을 더하면,

구하고자 하는 (2,3)~(3,4) 구간의 합이 나온다는 의미를 보여 주는 그림입니다.

오른쪽 표는 사전에 구해둔 구간합 표 입니다.

(1,1)~(1,4)의 부분합은 오른쪽 구간합 표에서 (1,4) 칸을 참조하면 되고,

(1,1)~(3,2)의 부분합은 오른쪽 구간합 표에서 (3,2) 칸을 참조하면 됩니다.

이렇게 구간합 표를 미리 구해두어서 굉장히 간편하게 소스코드를 작성할 수 있게 됩니다.

소스코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include <iostream>
#include <algorithm>

using namespace std;

int p_sum[1025][1025];

int main() {

	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M, num;
	cin >> N >> M;

    // 구간합 표 구하기
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> num;
			p_sum[i + 1][j + 1] = p_sum[i][j + 1] + p_sum[i + 1][j] - p_sum[i][j] + num;
		}
	}

    // 구해야 하는 구간을 입력받고 구간합 출력하기
	for (int i = 0; i < M; i++) {
		int x1, y1, x2, y2;
		cin >> y1 >> x1 >> y2 >> x2;

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

	}

	return 0;
}