백준 11659번 구간 합 구하기 4 / C++ / 누적합 (Prefix Sum)

알고리즘 개념: 누적합

누적합에 대해 잘 모른다면 이전에 정리해 둔 개념 정리를 한번 읽어보고 오는 것을 추천합니다. 

알고리즘 공부 3주차: 누적합 개념

알공 3주차: 누적합 개념

백준 11659번 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

문제

수 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

---

문제 설명

특정 구간의 합을 구하는 문제이다.

일일이 반복하여 계산하는 방식이 가장 쉽지만 수의 개수 N과 구해야하는 횟수 M의 최댓값이 100,000이므로 이것을 각 상황마다 하나하나 계산해서 더할 경우 최대 O(100,000^2)의 시간이 걸린다. 즉 시간초과가 난다. 

따라서 이중 for문을 사용하는 것이 아닌 누적합을 사용하는 것이 핵심이다. 

예제를 기준으로 설명해보면 누적합은 다음과 같이 만들 수 있다. 

예제 누적합1

예제 누적합2

예제 누적합3

그림에서는 cumarr이라는 새로운 배열을 만들었지만 내 코드에서는 그냥 arr배열을 수정하여 코드를 짰다. 

원리 자체는 간단해서 기존 arr배열의 값에서 이전의 값을 차곡차곡 더해주면 된다. 

for (int i = 1; i < n; i++) {
	arr[i] += arr[i - 1];
}

그럼 여기서 구간합은 어떻게 구할까? 

이미 누적합 개념 설명을 보고 오신 분들은 알겠지만 이것 또한 간단하다. 

1~3까지 더한 값은 인덱스 2번인 12이다. 인덱스는 0번부터 시작한다. 

2~4까지 더한 값은 4+3+2=9이므로 1~4까지 더한 값에서 첫번째 값을 빼주면 된다. 

즉 인덱스 3번(14)-인덱스 1번(5)를 빼면 답이 나온다. 

5~5인 경우 기존의 값인 1인데 이것 또한 1~5까지 더한 값에서 1~4까지 더한 값을 빼주면 된다. 

인덱스 4번(15)-인덱스 3번(14)=1

정리하자면 a와 b가 주어졌을때 a에서 b까지 더한 값을 구하는 공식은 다음과 같다. 

arr[b-1]-arr[a-2]

여기서 a의 범위는 1이상이므로 a가 1일때는 위 공식을 사용하는 것이 아닌 arr[b-1]을 해주면 된다. 

---

제출한 코드(C++)

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long int;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int arr[100005];
	int n, m;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	for (int i = 1; i < n; i++) {
		arr[i] += arr[i - 1];
	}
	int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		if (a >= 2) {
			cout << arr[b - 1] - arr[a - 2] << "\n";
		}
		else
			cout << arr[b - 1] << "\n";
	}
}