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

https://www.acmicpc.net/problem/11659

간단해보이는 문제지만, 그냥 생각나는 대로 이중 for문을 사용하면 시간초과가 발생하는 문제이다.

---

#include <iostream>
#include <vector>

using namespace std;

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

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

	vector<int> list = vector<int>(N, 0);
	vector<int> prefix = vector<int>(N, 0);
	vector<int> ans;

	for (int i = 0; i < N; i++)
		cin >> list[i];

	prefix[0] = list[0];

	for (int i = 1; i < N; i++)
		prefix[i] = prefix[i - 1] + list[i];

	for (int m = 0; m < M; m++)
	{
		int start, end;
		cin >> start >> end;

		if (start - 2 >= 0)
			ans.push_back(prefix[end - 1] - prefix[start - 2]);
		else
			ans.push_back(prefix[end - 1]);
	}

	for (int val : ans)
		cout << val << '\n';

	return 0;
}

누적 합 알고리즘을 사용해야 시간초과가 발생하지 않는다.

 

누적 합 알고리즘이란 간단하게 말해서 이전 값들의 합을 저장한 배열을 이용하는 것이다.

여기서는 prefix라는 벡터 배열을 이용하여 구현하였다.

어떤 구간을 구하고 싶으면 끝나는 인덱스와 시작지점 - 1의 인덱스를 빼주면 그 구간의 합이 구해지게 된다.