[Algorithm] 구간 합(prefix sum) 완.전.정.복

구간 합이란?

연속된 숫자들의 배열에서, 원하는 구간까지의 합을 알고자 할 때 이용하는 알고리즘.

ex) 1 ~ 10이 배열에 저장되어있다고 할 때, 합 배열은 1 3 6 10 ..과 같은 방식

합 배열에서의 1 = 1 / 3 = 1+2 / 6 = 1+2+3 / 10 = 1+2+3+4

 

if) 난 3 ~ 6의 합에 대해 알고 싶은데 어떻게 해야하나요?

answer) 1 ~ 6의 합에서 1 ~ 2의 합을 뺀다면, 원하는 답을 얻울 수 있어요!

 

공식

합 배열 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] (더하고자 하는 A[i]를, 이전까지의 합S[i-1]의 합)

 

구간 합을 구하는 공식

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

---

11659번: 구간 합 구하기 4

위의 개념을 숙지하고 이를 적용하기 매우 좋은 문제이다. 

말 그대로 구간합 내용을 사용하는 것이 포인트.

 

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<int> vec(N);
	vector<int> sum = { 0 };
	for (int i = 0; i < N; i++) {
		cin >> vec[i];
	}
	for (int i = 0; i < vec.size(); i++) {
		int hap = 0;
		hap = sum[i] + vec[i];
		sum.push_back(hap);
	} // 합 배열 공식 사용
	for (int i = 0; i < M; i++) {
		int x, y;
		cin >> x >> y;
		cout << sum[y] - sum[x - 1] << '\n';
	} // 구간 합 공식 시용

	return 0;
}

코드 리뷰는 언제나 환영.