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

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

11660번: 구간 합 구하기 5

 

솔루션

---

나는 이 문제를 보고 https://www.acmicpc.net/problem/24501 이 생각이 났다.

24501번: blobaww

사실 이 문제가 더 어렵지만, 먼저 푼 기억이 있어서, 나름 쉽게 접근 할 수 있었다.

 

2차원 배열에 각 지점의 합을 구하는데, 각 지점의 합은

(이전 행의 합 + 이전 열의 합) 을 하면, 중복이 되는 부분이있는데 (이전 행, 이전 열의 합)부분이 

중복이 된다. 따라서 현재배열의 값(arr[x][y]) + 이전 행의 총 합값(value[x-1][y]) +

이전 열의 총 합 값(value[x][y-1]) - 이전 행,열의 총 합 값(value[x-1][y-1])을 해 주어서

각 좌표지점에서의 총 합을 계산을 해 주었다.

 

그리고 x1,y1 ~x2,y2의 값을 구하기 위해서

x2,y2의 값에서 x1,y1의 이전 부분을 빼 주었다.

X
X	x1,y1
X
X
X			x2,y2

X	X	X	X
	x1,y1
			x2,y2

이렇게 빼 주면, x1-1,y-1부분이 중복으로 빼져서 value[x-1][y-1]을 다시 더해준다.

 

따라서 각 좌표에서 구하는 지점의 시간 복잡도를 O(1)로 구할 수 있다.

sum = value[x2][y2] - value[x1-1][y2] - value[x2][y1-1] + value[x1-1][y1-1];

을 해 주면 정답을 쉽게 구할 수 있다.

 

 

코드

---

#include <iostream>
using namespace std;

int arr[1026][1026];
int N, M;
int value[1026][1026];
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			cin >> arr[i][j];
			value[i][j] += (arr[i][j] - value[i - 1][j - 1] + value[i][j - 1] + value[i - 1][j]);
		}
	}
    
	for (int i = 0; i < M; i++) {
		int a, b, c, d;
		cin >> a >> b >> c >> d;
		int sum = value[c][d];
		sum -= (value[a-1][d] + value[c][b-1]);
		sum += value[a - 1][b - 1];
		cout << sum << "\n";
	}
}