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

문제 링크

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

17390번: 이건 꼭 풀어야 해!

 

문제

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

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

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

Figure 1.  모든 참가자가 문제를 풀 수 있을 것이라고 기대하는 욱제의 표정

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

입력

첫 번째 줄에 수열 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]이다.

힌트

비내림차순은 원소가 감소하지 않는 (같거나 증가하는) 순서를 말한다.

while (Q--) {
    int sum = 0, L, R;
    scanf(“%d %d”, &L, &R);
    for (int i = L; i <= R; i++) {
        sum += a[i];
    }
    printf(“%d\n”, sum);
}

위와 같이 각 질문마다 반복문을 매번 돌려서 답을 계산하면, 시간복잡도가 O(QN)이 되므로 시간 초과를 받게 된다. 다른 방법을 이용해 문제를 해결해야 한다.

알고리즘 분류

• 누적 합

풀이

비내림차순은 오름차순이라고 생각하고, N개의 수를 비내림차순으로 정렬한 후 누적 합을 구한다.

그리고 Q번에 걸쳐서 L부터 R까지의 구간의 누적 합을 구한다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 300001
#define LL long long
#define INF 1e12

using namespace std;
int N, Q;
vector<int> Vec;
LL Sum[MAX];
LL Answer = 0;

bool Comp(int A, int B) {
	return (A < B);
}

void Input() {
	cin >> N >> Q;
	for (int i = 0; i < N; i++) {
		int A;
		cin >> A;
		Vec.push_back(A);
	}
	sort(Vec.begin(), Vec.end(), Comp);
}

void Settings() {
	for (int i = 1; i <= N; i++) {
		Sum[i] = Sum[i - 1] + Vec[i - 1];
	}
}

void Find_Answer() {
	while (Q--) {
		int L, R;
		cin >> L >> R;
		cout << Sum[R] - Sum[L - 1] << "\n";
	};
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}