[알고리즘] 백준 11660번: 구간 합 구하기 5 (C++), 기하학적인 느낌(?)

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

11660번: 구간 합 구하기 5

 

아무 생각 없이 풀었다가 TLE가 나왔다.

[첫 시도]

각 행에서 누적합을 temp에 저장해 두고 명령을 내리면

합을 구하게끔 했지만 이마저도 TLE가 나온다.

 

>> TLE가 나온 이유는?

각 행의 누적합을 구해놓는다 한들 m이 가지는 최댓값이 100,000 표의 크기로 주어질 수 있는 최댓값이 1024로 1~1024행까지 구하는 명령이 100,000번 나오면 당연히 시간 초과가 난다.

#include <iostream>
#include <vector>
using namespace std;

int n, m;
int map[1025][1025];
int temp[1025][1025]; // 구간 합

int main() {
	cin >> n >> m;
	int idx;
	int value = 0;
	for (int i = 1; i <= n; i++) {
		value = 0;
		for (int j = 1; j <= n; j++) {
			cin >> idx;
			map[i][j] = idx;
			value += idx;
			temp[i][j] = value;
		}
	}

	for (int t = 0; t < m; t++) {
		int sum = 0;
		int x1, y1, x2, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		if (x1 == x2) {
			sum = temp[x2][y2] - temp[x1][y1 - 1];
		}
		else {
			for (int j = x1; j <= x2; j++) {
				sum += temp[j][y2] - temp[j][y1 - 1];
			}
		}
		cout << sum << '\n';
	}

	return 0;
}

 

[두 번째 시도 (솔루션)]

첫 시도에서는 각 행의 누적합을 담았었다. 이번엔 n행 m열까지의 누적합을 담아보기로 했다.

합을 구하는 과정은 아래 그림과 같다.

보라색 부분은 cache[n - 1][m]과 cache[n][m - 1]을 더하면서 cache[n - 1][m - 1]이 한 번 더 더해지기 때문에 보라색 부분을 빼줘야 한다.

cache[n][m] = cache[n - 1][m] + cache[n][m - 1] - cache[n - 1][m - 1] + value;

 

[AC 코드]

#include <iostream>
#define MAX 1024 + 1
using namespace std;

int n, m;
int cache[MAX][MAX];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> n >> m;

	int value;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> value;

			cache[i][j] = cache[i - 1][j] + cache[i][j - 1] - cache[i - 1][j - 1] + value;
		}
	}

	int x, y, x2, y2;
	for (int i = 0; i < m; i++) {
		cin >> x >> y >> x2 >> y2;
		cout << cache[x2][y2] - cache[x - 1][y2] - cache[x2][y - 1] + cache[x - 1][y - 1] << '\n';
	}

	return 0;
}

---

느낀 점

DP를 사용하긴 했지만 기하학적인 요소(?)도 첨가된 느낌이다.

최근 들어 입력을 받을 때 즉각적으로 어떤 기능을 수행하게끔 코드를 짜줘야 하는 문제들이 많았다.

(이러한 문제들이 대부분 시간 초과 방지 예방이었다.)

 

한 번쯤은 다시 업 솔빙 해봐야 할 문제인 듯하다.