[BOJ/C++] 17390 이건 꼭 풀어야 해!

시간 복잡도

• N과 Q가 최대 300,000 이므로 $O(N^2)$ 알고리즘을 사용하면 시간초과가 발생합니다.
• $O(nlogn)$ 시간 복잡도를 갖는 알고리즘으로 정렬 후 문제를 해결해야 합니다.

문제 접근법

• 정렬된 배열을 통해 구간 합 배열을 구합니다.
• 구간 합 배열 $S[i]$는 $1~i$까지의 합을 의미하므로 $L~R$ 구간의 합을 알기 위해선 $1~R$ 구간에서 $1~L-1$ 구간을 빼면 됩니다.
• 즉 $S[R]-S[L-1]$ 구하면 문제를 해결할 수 있습니다.

코드

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <string>
#include <climits>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>

using namespace std;

using int32 = long;
using int64 = long long;

static vector<int> A;
static vector<int> S;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    A.resize(N+1);
    S.resize(N+1);

    for(int i=1; i<=N; i++)
        cin >> A[i];

    sort(A.begin(), A.end());

    for (int i = 1; i <= N; i++)
        S[i] = S[i - 1] + A[i];

    for(int i=0; i<Q; i++)
    {
        int L, R;
        cin >> L >> R;

        cout << S[R] - S[L-1] << '\n';
    }


    return 0;
}