[11660] 구간 합 구하기 5

---

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

11660번: 구간 합 구하기 5

누적합 + 동적 프로그래밍 문제이다.

 

처음에 푼 것과 다시 푼 것 모두 설명해보려 한다.

 

 

1. 행 누적합

행과 열을 합쳐서 누적합을 구하기 어렵다고 판단하여 행의 누적합을 2차원 배열에 담았다.

A[i][j]를 i행에서의 1~j열까지의 합으로 정의하였다.

 

예를 들어

A[1][3] = 1 + 2 + 3 = A[1][2] + 3 = 6

A[4][2] = 4 + 5 = A[4][1] + 5 = 9

이다.

 

 

주어진 구간 내에서 누적 합을 구할 때에는 각 행의 누적합의 합에서 필요없는 부분을 빼주는 방식으로 진행하였다.

#include <iostream>
using namespace std;

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

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++) {
			int tmp; cin >> tmp;
			A[i][j] = A[i][j - 1] + tmp;
		}
	}

	for (int i = 1; i <= M; i++) {
		int r, c, rr, cc; int sum = 0;
		cin >> r >> c;
		cin >> rr >> cc;
		for (int j = r; j <= rr; j++) {
			sum += A[j][cc];
			sum -= A[j][c - 1];
		}
		printf("%d\n", sum); // cout 쓰면 시간초과
	}
}

맞았긴 했는데 좀 찜찜했다. cout을 쓰면 시간초과가 났기 때문이다.

그래서 다시 풀어보았다.

 

 

 

2. 행, 열 누적합

행과 열을 합쳐서 누적합을 구하는 방법을 생각해보았다.

A[i][j]를 새롭게 정의해주었다.

A[i][j]를 A[1][1]부터 A[i][j]까지의 직사각형 박스의 누적합으로 정의하였다.

 

예를 들어

A[2][3]은 파란색 직사각형 박스의 합인 것이다.

 

규칙은 직접 다양한 예시를 들어보며 찾았다.

A[i]][j]에서 A[i-1][j-1]를 빼준 이유는 A[i][j-1]와 A[i-1][j]에서 중복으로 더해졌기 때문이다. 

 

주어진 구간의 누적합을 구할 때에 A[x1-1][y1-1]를 더해준 이유는 A[x2][y1-1]와 A[x1-1][y2]에서 중복으로 빼주었기 때문이다.

직접 그려보면서 하면 이해가 된다!

#include <iostream>
using namespace std;

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

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++) {
			int tmp; cin >> tmp;
			A[i][j] = A[i - 1][j] + A[i][j - 1] - A[i - 1][j - 1] + tmp;
		}
	}

	for (int i = 1; i <= M; i++) {
		int r, c, rr, cc;
		cin >> r >> c;
		cin >> rr >> cc;
		printf("%d\n", A[rr][cc] - A[rr][c - 1] - A[r - 1][cc] + A[r - 1][c - 1]);
	}
}

시간이 줄어든 것을 확인할 수 있다!