[백준/C++] 11659번 : 구간 합 구하기 (누적합 문제)

구간 합 구하기 

문제

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

입력

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

출력

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

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

예제 입력 1 

5 3
5 4 3 2 1
1 3
2 4
5 5

예제 출력 1 

12
9
1

---

누적합 문제를 처음 풀어봤다.

처음엔 단순 for문을 이용한 합계를 구해 시간초과가 발생했다.

 

#include <iostream>
#include <string>
#include <vector>

using namespace std;

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

	int N, M;
	cin >> N >> M;
	vector<int> nums(N+1);
	for (int i = 1; i <= N; i++)
	{
		cin >> nums[i];
		nums[i] = nums[i - 1] + nums[i];
	}

	while(M--)
	{
		int start, end;
		cin >> start >> end;

		cout << nums[end] - nums[start-1] << '\n';
	}

	return 0;
}

 

시간초과를 없애기 위해선, for문을 통해 합계를 구하는 부분을 빼야한다.

 

누적합이라는 문제 유형 그대로, 배열 nums에는 누적되는 수의 합들을 저장했다.

0번째 인덱스는 첫번째 입력 숫자만 들어가지만, 1번째 인덱스는 첫번째 + 두번째 숫자의 합이 들어가고 2번째 인덱스는 1번 인덱스 + 세번째 숫자의 합이 들어간다.

 

이런식으로 누적합을 배열에 저장하고, 나중에 일정 범위 내 수의 합을 출력할 땐 "끝 범위 - 시작 범위-1" 연산을 수행했다.

 

예를 들어 3부터 5까지 수의 합을 구하고 싶다면 1~5의 합에서 1~2의 합을 빼면 된다는 것이다.

시작범위를 그대로 넣으면 3이 겹쳐지기 때문에 꼭 시작범위-1을 해주어야 한다.

---

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

11659번: 구간 합 구하기 4