(백준/C++) 11659_구간 합 구하기 4

누적 합 문제는 구간에 있는 수의 합을 빠르게 계산하기 위한 방법입니다.

11659번: 구간 합 구하기 4 (acmicpc.net) 문제는 1차원 배열에서 특정 구간의 합을 빠르게 계산하기 위한 방법을 묻는 문제입니다.

이는 $O(N)$의 시간 복잡도로 누적 합 배열을 생성하고, 특정 구간의 합을 $O(1)$의 시간 복잡도로 계산할 수 있습니다.

로직 설계

이 문제는 i번째 수부터 j번째 수까지 합을 M번 구하는 문제입니다.

단순한 방법으로는 $O(N^2)$의 시간 복잡도를 가지기 때문에 이 시간 복잡도를 줄여야 하고, 또한 부분 구간 안의 수의 합을 계산해야 합니다.

이를 해결하는 방법으로 단계별로 합을 누적해 저장하는 방식으로 해결할 수 있습니다.

구간 합의 개념

누적 합은 생각보다 단순하지만, 먼저 구간 합을 구하는 방법부터 보겠습니다.

(3~4)구간은 (1~4)구간에서 (1~2)구간을 빼는 것으로 구할 수 있습니다.

따라서, 만약 수를 누적해서 저장한다고 한다면, 두 누적 합의 계산만으로 구간 합을 쉽게 구할 수 있게 됩니다.

---

풀이

따라서, 구간 합을 구하기 위해서는, 누적 합을 저장할 수 있는 배열을 만들고, 두 위치에 존재하는 구간 합의 차를 이용해 쉽게 구할 수 있습니다.

#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> nums(N);
	vector<int> prefixSum(N + 1, 0);

	//구간합 미리 구해두기
	for(int i = 0; i < N; i++)
	{
		cin >> nums[i];
		prefixSum[i + 1] = prefixSum[i] + nums[i];
	}

	while(M--)
	{
		int i, j;
		cin >> i >> j;
		//두 구간의 구간합 차 사용
		cout << prefixSum[j] - prefixSum[i-1] << '\n';
	}
}