백준 17390번 이건 꼭 풀어야해! / C++ / 누적합 (Prefix Sum)

알고리즘 개념 누적합

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

[알고리즘] 누적합 (prefix sum)

[알고리즘] 누적합 (prefix sum)

 

백준 17390번 이건 꼭 풀어야해!

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

17390번: 이건 꼭 풀어야 해!

문제

숭실골 높은 언덕 깊은 골짜기에 출제로 고통 받는 욱제가 살고 있다!

욱제는 또 출제를 해야 해서 단단히 화가 났다. 그래서 욱제는 길이 N짜리 수열 A를 만들고, A를 비내림차순으로 정렬해서 수열 B를 만들어 버렸다!! 여기서 B를 출력하기만 하면 문제가 너무 쉬우니까 하나만 더 하자. 아래와 같은 질문이 무려 Q개나 주어진다!! (ㅎㅎ;; ㅈㅅ.. ㅋㅋ!!)

• L R: BL + BL+1 + ... + BR-1 + BR 을 출력한다.

입력

첫 번째 줄에 수열 A의 길이 N과 질문의 개수 Q가 공백으로 구분되어 주어진다. (1 ≤ N, Q ≤ 300,000)

두 번째 줄에 N개의 정수 A1, A2, ..., AN 이 공백으로 구분되어 주어진다. Ai 는 수열 A의 i 번째 수이다. (1 ≤ Ai ≤ 1,000)

세 번째 줄부터 Q개의 줄에 걸쳐 욱제의 질문을 의미하는 두 수 L, R이 공백으로 구분되어 주어진다. (1 ≤ L ≤ R ≤ N)

주어지는 모든 입력은 자연수이다.

 

출력

Q개의 줄에 걸쳐, 질문의 답을 순서대로 각각 출력한다.

예제 보려면 더보기 클릭

예제 입력 1

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

예제 출력 1

15
9
3
6
14
9

[2, 5, 1, 4, 3]을 비내림차순으로 정렬하면 [1, 2, 3, 4, 5]이다.

 

예제 입력 2

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

예제 출력 2 

5
4
13

[2, 5, 1, 2, 3]을 비내림차순으로 정렬하면 [1, 2, 2, 3, 5]이다.

---

문제 설명

예제 1번을 예시로 설명해보면 

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

길이는 n인 배열과 문제의 갯수 q가 주어진다. 

1 5인 경우 1번~5번까지의 합

2 4인 경우 2번~4번까지의 합

3 3인 경우 3번~3번까지의 합

반복문을 통해 하나하나 계산하는 방식도 있지만 수의 개수 N과 문제의 갯수 Q의 최댓값이 300,000이므로 이것을 각 상황마다 하나하나 계산해서 더할 경우 최대 O(300,000^2), 시간초과가 난다. 

따라서 누적합 배열을 사용하는 것이다. 

예제 누적합 설명1

예제 누적합 설명2

예제 누적합 설명3

예제 누적합 설명4

이렇게 각 arr인덱스에서 이전 arr의 값들을 더해가며 누적합을 구할 수 있다. 

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

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

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

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

인덱스 2번(8)-인덱스 1번(7)=1

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

arr[r-1]-arr[l-2]

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

 

---

제출한 코드(C++)

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
vector <int> arr;
int main(void) {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	int n, q;
	int l, r;
	cin >> n >> q;
	int a;
	for (int i = 0; i < n; i++) {
		cin >> a;
		arr.push_back(a);
	}
	sort(arr.begin(), arr.end());//오름차순정렬
	for (int i = 1; i < arr.size(); i++) {
		arr[i] += arr[i - 1];
	}
	for (int i = 0; i < q; i++) {
		cin >> l >> r;
		if (l == 1)
			cout << (arr[r - 1]) << "\n";
		else
			cout << (arr[r - 1] - arr[l - 2]) << "\n";
	}


	return 0;
}