[BOJ] 11660 구간 합 구하기 5

📍문제 분석 및 프로그램 설계

2차원의 배열, 즉 정사각행렬이 주어지고 그 요소들의 값이 주어진다. 그리고 x1, x2, y1, y2가 주어지고 행렬의 행과 열의 크기인 N이 주어지면 (x1, y1)부터 (x2, y2)까지의 sub matrix의 요소값들의 합을 입력받은 M의 횟수만큼 출력한다.
원하는 범위만큼 2중 for문을 써서 하나하나 접근+더해서 값을 출력해도 되지만 시간복잡도 상 그렇게 하면 시간초과가 되므로 누적합이라는 것을 사용을 한다.

💡문제를 해결하는데 필요한 개념

누적합의 개념. 단순히 값들을 전부 저장하고 일일이 전부 더하는 것이 아닌 값들의 합들을 누적시킨 누적합을 저장하고 접근하는 것이 시간적으로 유리하다.

💻소스 코드

#include <iostream>

using namespace std;

int v1[1025][1025], v2[1025][1025];

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N, M;
	
	cin >> N;
	cin >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> v1[i][j];
			v2[i][j] = v2[i - 1][j] + v2[i][j - 1] - v2[i - 1][j - 1] + v1[i][j];
		}
	}

	while (M--) {
		int x1, x2, y1, y2;
		int sum;

		cin >> x1 >> y1 >> x2 >> y2;
		x1--; x2--; y1--; y2--;

		sum = v2[x2][y2] - v2[x1 - 1][y2] - v2[x2][y1 - 1] + v2[x1 - 1][y1 - 1];
		cout << sum << '\n';

	}

	return 0;
}

👌문제를 풀기 위해 생각하고 해결했던 과정 및 느낀점

우선 문제를 처음 보고 생각난 것은 다름 아닌 범위의 값을 for문을 통해 전부 순회하고 그 값들을 다 더해서 출력을 하는 것이다. 하지만 당연하게도 시간초과가 떴고 시간을 줄일 수 있는 다른 방법을 생각해 보았다.
그렇게 혼자 생각을 하다가 도저히 떠오르지 않아 구글링 후 누적합이라는 것을 알게되었다.
예를 들어 {1, 2, 3, 4}의 값을 더해서 {1, 3, 6, 10}을 구한다고 하면
{1, 1+2, 1+2+3, 1+2+3+4} 이런 식으로 구하는 것이 아니라 그 전 단계의 누적된 합을 이용하여 {1, 1+2, 3+3, 6+4} 이런식으로 구하는 것이 이렇게 적은 범위에서 봐도 더 좋아보인다.

그래서 누적합을 이용하여 문제를 풀려고 시도를 하였다. 위 예시와 다르게 이 문제는 2차원 배열, 즉 행렬이다. 그러니 단순히 가로로만 누적합을 적용하는 것이 아닌 가로와 세로 둘다 적용을 해야한다.

그래서 우선 주어진 행렬자체의 값을 그대로 저장하는 배열(v1)을 만들고 그것을 통해 누적합을 저장하는 배열(v2)을 만들었다.

여기서 주의해야 할 점이 있었다. 누적합을 저장할 행과 열의 바로 전 누적합들([i-1][j]와 [i][j-1]) 그리고 원래 그 자리의 값을 다 더한 후 중복값을 빼줘야 한다. 그렇지 않으면 두번 중복 되기에 정확한 누적합이 아니게 된다.

그런식으로 누적합을 구한 후 원하는 범위에서의 값들의 합은 누적합 행렬의 [0][0]부터 범위의 상한까지의 누적합에서 범위에 해당하지 않는 부분들을 빼고 두번 빼진 중복값을 더해주기만 하면 구할 수 있다.
하지만 이렇게 했음에도 시간초과가 계속하여 발생하였고 또 한번의 구글링 결과 아래와 같은 코드들을 넣었다.

    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

찾아보니 전부 입출력 시간을 줄여주는 역할을 하는 것이였다.(buffer관련된 것들인 것 같다.)
이 코드 세줄을 넣음으로써 문제를 풀 수 있게 되었다.