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

 

 

문제 링크

11660번: 구간 합 구하기 5

(x1,y1)부터 (x2,y2) (x1<=x2, y1<=y2)까지의 합을 구하는 문제이다.

배열의 크기가 최대 1,024x1,024로 크다고는 생각하지 않았지만 문제는 구간 합을 구하는 횟수였다.

최대 100,000번 계산해야 하기 때문에 단순하게 해당 범위를 모두 구하려면

최대 1,024x1,024x100,000번의 계산이 필요하기 때문에 해당 방법은 적절하지 못한 것 같았다.

 

우선 (1,1)부터 (x,y)까지의 합을 total[x][y]로 하는 배열 total을 구성하고,

total의 원소간의 계산을 통해 (x1,y1)부터 (x2,y2)까지의 합을 구하는 방법을 생각해 냈다.

문제의 예시에선 다음과 같이 4x4의 행렬을 제시해 줬다.

이를 토대로 (1,1)부터 (x,y)까지의 합을 나타내는 배열 total을 한번 작성해 보았다.

total[1][j]와 total[i][1]은 한개의 행, 한개의 열로 이루어져 있기 때문에 계산하기 쉬울 것 같았다.

그러나 여러 행 또는 여러 열로 이루어진 원소에 대해서는 생각해 보아야 했다.

 

우선 다른 원소에 비해 값이 작은 total[2][2]를 구해보고자 했다.

뭔가 total[2][2]의 왼쪽 원소와 위쪽 원소가 관련이 있을까 싶어 무작정 a[2][2]와 더해보았다.

a[2][2]+total[1][2]+total[2][1]=9

그러고 보니 total[2][2]보다 1 큰 값이 나왔다. 바로 a[1][1]이다.

 

그 이유는 total[1][2]=a[1][1]+a[1][2]이고, total[2][1]=a[1][1]+a[2][1]이기 때문에

total[1][2]+total[2][1]을 하면 a[1][1]이 두번 더해진 것이다.

그래서 total[2][2]보다 딱 a[1][1]만큼 큰 값이 나온것이다. (합집합의 원소의 개수를 구하는 식과 비슷했다.)

total[2][2], total[1][2], total[2][1]을 각각 배열 a에 빨간색, 초록색, 파란색으로 표현한 모습 a[1][1]이 겹친다

따라서 다음 식을 적용하면 모든 total에 대해 계산이 가능할 것 같았다.

total[i][j]=a[i][j]+(왼쪽)+(위쪽)-(겹치는 부분)

여기서 문제는 겹치는 부분이 어디인가인데 몇번 다른 원소로 계산하고 보니 total[i][j]의 왼쪽 위 원소가 되었다.

 

따라서 total[i][j]=a[i][j]+total[i-1][j]+total[i][j-1]-total[i-1][j-1]로 total의 모든 원소를 구할 수 있었다.

위 식은 왼쪽, 위쪽, 왼쪽 위 대각 원소가 존재하는 경우에만 계산하는 방식으로

첫번째 행이나 첫번째 열에 대해서도 적용할 수 있다.

 

의사 코드로 표현하자면 다음과 같다.

total[i][j] = a[i][j];
if(total[i][j]의 왼쪽이 존재한다면)
	total[i][j]+=total[i][j]의 왼쪽
if(total[i][j]의 위쪽이 존재한다면)
	total[i][j]+=total[i][j]의 윗쪽
if(total[i][j]의 왼쪽 위 대각이 존재한다면)
	total[i][j]-=total[i][j]의 왼쪽 위 대각

 

이렇게하여 (1,1)부터 (x,y)까지의 합 total[x][y]를 구했다. 이를 이용하여 (x1,y1)부터 (x2,y2)까지의 합을 구하고자 한다.

예시삼아 (2,2)부터 (3,3)까지의 합을 구해보도록 하겠다.

구하고자하는 부분(빨간색)과 total[2][2](초록색)를 배열 a위에 표현한 모습 

total을 최대한 이용하기 위해 초록 부분에서 빨간 부분만을 떼어내고자 한다.

빨간 박스의 왼쪽은 total[3][1]과 유사하다. 빨간 박스의 위쪽은 total[1][3]과 유사하다.

total[3][3]-total[1][3]-total[3][1]을 하고 나니 total[3][1]과 total[1][3]과 겹치는 부분인 a[1][1](=total[1][1])이 두번 빼지게 된다. 그래서 한번 더해주겠다.

total[3][3]-total[1][3]-total[3][1]+total[1][1]=16으로 잘 나왔다.

 

문제의 예시로 들은 (2,2)부터 (3,4)까지의 합 또한

total[3][4]-total[1][4]-total[3][1]+total[1][1]=27로 예시의 답과 같다.

 

(4,4)부터 (4,4)까지의 합도

total[4][4]-total[3][4]-total[4][3]+total[3][3]=7로 예시의 답과 같다.

 

따라서 (x1,y1)부터 (x2,y2)까지의 합은 다음과 같이 표현할 수 있다.

total[x2][y2]-total[x1-1][y2]-total[x2][y1-1]+total[x1-1][y1-1]

 

소스코드는 다음과 같다.

#include <iostream>

using namespace std;

int a[1025][1025], total[1025][1025];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		a[0][i] = 0;
		a[i][0] = 0;
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			total[i][j] = a[i][j];
			if (i - 1 >= 1) {
				total[i][j] += total[i - 1][j];
			}
			if (j - 1 >= 1) {
				total[i][j] += total[i][j - 1];
			}
			if (i - 1 >= 1 && j - 1 >= 1) {
				total[i][j] -= total[i - 1][j - 1];
			}
		}
	}
	while (m--) {
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		int result = total[x2][y2] - total[x2][y1 - 1] - total[x1 - 1][y2] + total[x1 - 1][y1 - 1];
		cout << result << "\n";
	}
	return 0;
}