[백준 17390] 이건 꼭 풀어야 해! (C++)

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

문제

---

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

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

• L R: B_L + B_L+1 + ... + B_R-1 + B_R 을 출력한다.

욱제의 질문에 답하고 함께 엠티를 떠나자!!

 

입력

---

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

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

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

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

 

출력

---

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

 

문제 풀이

---

정렬+누적합 문제.

 

비내림차순이므로 오름차순으로 정렬하면 된다. 그 이후는 L부터 R까지의 합을 구해야 하는데, 질문의 개수가 최대 300,000개이므로 L부터 R까지 반복문으로 구하면 시간 초과가 발생한다. 미리 A₀부터 A_i까지의 합을 구한 배열을 만들어 저장한 후, L 이전의 값들을 모두 빼주면 된다.

 

아래는 코드.

#include <iostream>
#include <algorithm>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, M;
	int a, b;
	cin >> N >> M;
	int* arr = new int[N];
	int* sum = new int[N+1];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	sort(arr, arr + N);
	sum[0] = 0;
	for (int i = 0; i < N; i++)
	{
		sum[i + 1] = sum[i] + arr[i];
	}
	for (int i = 0; i < M; i++)
	{
		cin >> a >> b;
		cout<<sum[b] - sum[a-1]<<"\n";
	}
	return 0;
}