[C++]백준 11659. 구간 합 구하기 4

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

구상

매번 각 구간의 합을 계산하면 1억 회 이상의 연산을 수행할 가능성이 있다.

구간 합을 저장하는 배열을 만들어 놓고 필요할 때마다 꺼내 쓰면 된다.

 

구간 합의 개념을 간단하게 살펴보자.

입력받은 수	5	4	3	2	1
구간 합	5	9	12	14	15

 

표만 봐도 감이 올 것이다. 주어진 수열을 차례대로 더해서 만든 새로운 수열이 바로 구간 합이다.

구간 합을 배열의 형태로 풀어보면

 

수 배열	A[0]	A[1]	A[2]	A[3]	A[4]
	5	4	3	2	1
구간 합 배열	S[0]	S[1]	S[2]	S[3]	S[4]
	5	9	12	14	15

 

위와 같은 형태가 될 것이다.

수 배열에서 구간 합 배열을 만드려면 이 때까지 구한 구간 합에 수 배열의 수를 하나 더해주면 된다.

즉, S[i] = S[i - 1] + A[i] 가 된다. 

 

구간 합 배열에서 원하는 구간 합을 구하려면 어떻게 해야 할까?

A[1], A[2], A[3] 구간의 합을 알고 싶다면,

A[0] + A[1] + A[2] + A[3] - A[0]와 같으므로 S[3] - S[0]를 계산하면 된다.

일반화하면 구간 a, b의 구간 합은 S[b]  - S[a - 1]이다.

 

그런데, 이 배열에서 만약 A[0], A[1] 구간의 합을 알고 싶을 때는 문제가 발생한다.

공식에 대입하면 S[1] - S[-1]이 되어 인덱스가 음수가 되어버린다.

이 문제를 해결하려면 배열의 크기를 하나 늘려서 0을 저장하는 배열을 만들어 버리면 된다.

 

수 배열	A[0]	A[1]	A[2]	A[3]	A[4]	A[5]
	0	5	4	3	2	1
구간 합 배열	S[0]	S[1]	S[2]	S[3]	S[4]	S[5]
	0	5	9	12	14	15

 

이제 프로그램을 작성해보자.

수를 입력 받아 구간 합 배열을 완성하고 테스트 케이스에 맞게 출력하면 끝이다.

 

vector<int> prefixSum(n+1);	//0을 저장하기 위해 size는 n + 1
for (int i = 1; i <= n; i++) {	//새로운 수는 두 번째 원소부터 저장
	int num;	//구간 합 배열만 있으면 되므로
	cin >> num;	//수 배열을 굳이 사용할 이유 없음
	prefixSum[i] = prefixSum[i - 1] + num;
}

for (int i = 0; i < m; i++) {
	int a, b;
	cin >> a >> b;
	cout << prefixSum[b] - prefixSum[a - 1] << "\n";	//구간합 출력
}

 

구간 합 배열을 만들 때 수 배열을 사용했으니 프로그램을 작성할 때도 수 배열에다가 수를 몽땅 입력받고 다시 값을 꺼내 구간 합을 만들 수도 있지만, 그러지 않고 수를 입력받을 때마다 구간 합에 바로바로 합산하면 수 배열이 없어도 된다.

 

코드

 

#include <iostream>
#include <vector>

using namespace std;

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

	int n, m;
	cin >> n >> m;
	
	vector<int> prefixSum(n+1);	//0을 저장하기 위해 size는 n + 1
	for (int i = 1; i <= n; i++) {	//새로운 수는 두 번째 원소부터 저장
		int num;	//구간 합 배열만 있으면 되므로
		cin >> num;	//수 배열을 굳이 사용할 이유 없음
		prefixSum[i] = prefixSum[i - 1] + num;
	}

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		cout << prefixSum[b] - prefixSum[a - 1] << "\n";	//구간합 출력
	}

	return 0;
}