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

문제링크 : https://www.acmicpc.net/problem/17390

17390번: 이건 꼭 풀어야 해!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, Q, arr[300001];
int L, R;

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

    cin >> N >> Q;
    for(int i=1; i<=N; i++) cin >> arr[i];
    sort(arr+1, arr+N+1); //비내림차순 정렬
    for(int i=1; i<=N; i++) arr[i]+=arr[i-1]; //누적합

    while(Q--)
    {
        cin >> L >> R;
        cout << arr[R] - arr[L-1] << "\n";
    }
    
}

 

이중 반복문(O(QN))으로 풀면 시간초과가 나기에 누적합을 응용하여 푼 문제이다.

수열을 입력받고 비내림차순 정렬을 먼저 해준 이후에 누적합을 구해준다.

 

우리가 구하고자하는 것은 L~R의 일정 구간의 합이므로, R까지의 합 - (L-1)까지의 합을 구해주면 된다.

<2, 4>
(1+2+3+4) - (1)

<3, 4>
(1+2+3+4) - (1+2)