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

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

11660번: 구간 합 구하기 5

문제

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

예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.

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

표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)

출력

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

---

풀이

누적합 문제인데 2차원이라서 해결책을 찾는 게 조금 어려웠다.

 

위 문제를 예로 들어보자면 초기값으로 일단 1행과 1열은 채워준 후에

(2,2)의 누적합은 (1,1)에서 (2,2)까지이니

 

입력값은 3이고 , x자리에 들어갈 것은 (1,2) 누적합과 (2,1)의 누적합과 입력값을 더해주면 된다. 여기서 주의해야 할 점은

(1,2) 과 (2,1) 값에는 (1,1)이 중복되어 들어가기에 (1,1)의 값은 더해줘야 한다.

 

즉, (2,2)의 누적합 = (1,2) + (2,1) + 입력값 - (1,1)

일반식으로 나타내면

(x,y) =  (x-1,y) + (x,y-1) + input - (x-1,y-1)이다. 

 

글로 보니 어렵네요? 그림으로 보면 조금 이해될꺼예요 ..

 

 

이제 누적합을 다 채울수 있으니 예제의 (2,2) 에서 (3,4)의 값을 구해보자면

이를 구하려면 

여기서 두 번 빼준 (1,1)값을 더해주면 된다.

 

식으로 나타내면

(2,2)~(3,4) = (3,4)누적합 - (1,4)누적합 - (3,1)누적합 + (1,1)누적합

 

일반식으로

(x1,y1) ~ (x2,y2) = (x2,y2) - (x1-1,y2) - (x2,y1-1) + (x1-1,y1-2) 이다 . 

---

#include <bits/stdc++.h>
using namespace std;
int sum[1025][1025] = { 0, };

int main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int cnt = 0; 
	int inp = 0;
	cin >> cnt >> inp;

	int tmp = 0;
	for (int i = 1; i <= cnt; i++) {
		for (int j = 1; j <= cnt; j++) {
			cin >> tmp;
			sum[i][j] = tmp + sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1]; // 구간합 
		}
	}

	for (int i = 0; i <inp; i++) {
		int x1, x2, y1, y2;
		cin >> y1 >> x1 >> y2 >> x2;
		cout << sum[y2][x2] - sum[y2][x1 - 1] - sum[y1 - 1][x2] + sum[y1 - 1][x1 - 1]<<'\n'; 
		// 중복으로 빼준거 더해주기 꼭 !
	}

	return 0;
}