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

11660번: 구간 합 구하기 5

문제 분석

문제는 2차원 배열안에서 (x1,y1) 에서 (x2, y2)의 합을 구하는 문제이다.

원소 하나하나를 더하기보다, 구간마다의 합을 더해서 연산의 속도를 최대한 빠르게 하는 것이 포인트.

즉, 구간 합에 대해 알고 있어야 하는 문제이다.

 

구간 합이란?

합 배열 S의 정의

S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i] (A[0]부터 A[i]까지의 합)

이라고 할 때, 

 

합 배열 S를 만드는 공식

S[i] = S[i-1] + A[i]

의 특징을 지니게 된다.

이를 응용해서 원하는 구간까지의 합을 구할 수 있다!

 

구간 합을 구하는 공식

S[j] - S[i-1] (i에서 j까지의 구간 합)

---

C++ (첫 번째 풀이)

#include <iostream>
#include <vector>

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M;
	cin >> N >> M;
	vector<vector<int>> vec(N, vector<int>(N, 0)); // vec : 처음 주는 입력값의 배열
	vector<vector<int>> sum(N, vector<int>(N, 0)); // sum : 구간합의 배열

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> vec[i][j];
			if (j == 0) {
				sum[i][j] = vec[i][j];
			}
			else {
				sum[i][j] = sum[i][j - 1] + vec[i][j];
			}
		}
	}
    // 입력받음과 동시에 sum의 배열을 대입함.
    // 한 행의 합만을 구해야하기 위한 조건 작성함.

	for (int i = 0; i < M; i++) {
		int x1, y1, x2, y2;
		int hap = 0;
		cin >> x1 >> y1 >> x2 >> y2;
		for (int j = x1; j < x2 + 1; j++) {
			if (y1 - 2 < 0) {
				hap += sum[j - 1][y2 - 1];
			}
			else {
				hap += sum[j - 1][y2 - 1] - sum[j - 1][y1 - 2];
			}
            // 합 구할 때, 인덱스가 0보다 작이질 경우에 대한 조건문 작성
		}
		cout << hap << '\n';
	}

	return 0;
}

1	3	6	10
2	5	9	14
3	7	12	18
4	9	15	22

위의 코드에서 sum을 표현한 표이다. 나는 행에 대한 구간 합만을 사용했고, 이를 x,y에 대한 입력을 받을 때, 원하는 구간끼리의 합을 합치도록 실행하였다.

이는 정답이 되기는 하나, 최적화된 코드는 아니라고 할 수 있다. (파이썬은 이와 같이 코딩할 경우 틀림)

---

최적화된 코드를 위해서는 비슷하지만 다른 구간 합의 방식을 사용해야 한다.

1	2	3	4		1	3	6	10
2	3	4	5		3	8
3	4	5	6		6
4	5	6	7		10

위 방식처럼 x,y의 좌표를 받았을 때, (1,1) 부터 (x,y)에 대한 내부의 구간 합을 구하는 방식이다.

(2,2)에서의 8에 대해 살펴보자

1 + 2 + 2 + 3 = 8을 구간 합의 방식으로 표현하는 것이다.

이를 입력배열에서의 인덱스로 표현하면

1,1 + 1,2 + 2,1 + 2,2 = 8이다.

 

이번에는 구간합을 이용한 풀이방식이다. 위와 같이 원소를 직접 대입해서 더한다면 연산자가 많아져 코드의 시간복잡도가 길어진다. 이는 구간합을 활용하면 연산자를 쉽게 줄일 수 있다.

만약 구간합에서의 (2,2)를 구한다면?

8 = 3(2,1) + 3(1,2) + 3(2,2) - 1(1,1)

구간합 배열에서의 (1,2)와 (2,1)은, 각각 입력배열에서의 (1,1) + (1,2) / (1,1) + (2,1) 와 같다.

 

1,1 + 1,2 + 2,1 + 2,2 = (1,1 + 2,1) + (1,1 + 1,2) + (2,2) - (1,1)

위 식을 보면 이해가 편한가? 이처럼 더하게 된다면 1,1이 한번 더 더해지므로, 1,1을 한번 빼줘야한다.

이 방식을 구간합 배열에서의 다른 원소들을 구할 떄에도 똑같이 적용하면 된다.

⭐ S[i][j] = S[i-1][j] + S[i][j-1] + A[i][j] - S[i-1][j-1]

 

이번에는 내가 원하는 구간 합을 구한다.

구간 합 배열에서의 원소는 처음부터 원하는 위치의 직사각형 넓이이다.(x2, y2)

이때 이 안의 원하는 곳을 구하고자 한다면, ((x1, y1)으로 정해진다면?)

x1 - 1, y2 / x2, y1 - 1의 원소를 빼주고, x1 - 1, y1 - 1의 원소를 더해주면 원하는 곳의 넓이를 구할 수 있다.

⭐ 원하는 넓이 = S[x2[[y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1]

 

C++ 두 번쨰 풀이

#include <iostream>
#include <vector>

using namespace std;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int N, M;
	cin >> N >> M;
	vector<vector<int>> vec(N + 1, vector<int>(N + 1, 0));
	vector<vector<int>> sum(N + 1, vector<int>(N + 1, 0));
    // 처음 벡터를 선언할 떄, 기존 입력값의 배열 크기보다 크게 잡음
    // 0을 넣어두기 위해서

	for (int i = 1; i < N + 1; i++) {
		for (int j = 1; j < N + 1; j++) {
			cin >> vec[i][j];
			if (i == 0 && j == 0)
				sum[0][0] = vec[0][0];
			else if (i == 0 && j != 0)
				sum[i][j] = sum[i][j - 1] + vec[i][j];
			else if (j == 0 && i != 0)
				sum[i][j] = sum[i - 1][j] + vec[i][j];
			else
				sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + vec[i][j] - sum[i - 1][j - 1];
				// 전체 구간 합 구하기
        }
        // 인덱스 i, j가 각각 0일때에 대해서 경우를 나눠두었다.
	}

	for (int i = 0; i < M; i++) {
		int x1, y1, x2, y2;
		int result = 0;
		cin >> x1 >> y1 >> x2 >> y2;
		
		result = sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1];
		// 원하는 구간 계산하기
		cout << result << '\n';
	}


	return 0;
}

아래는 첫번째 풀이, 위에는 두번째 풀이이다. 보면 시간복잡도의 차이가 확연히 난다는 것을 알 수 있다.

 

코드 리뷰는 언제나 환영입니다.