[Algorithm] BAEKJOON 17390번: 이건 꼭 풀어야 해! (C++)

https://www.acmicpc.net/problem/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개의 줄에 걸쳐, 질문의 답을 순서대로 각각 출력한다.

 

 

 

 

풀이

매 질문마다 반복문을 계속 돌려서 풀어주면 시간 초과가 나므로 먼저 수열을 비내림차순으로 정렬한 다음 누적 합을 이용해서 풀어주면 된다.

 

 

C++ 소스 코드

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

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

    int N, Q, L, R;  // N: 수열 A의 길이, Q: 질문의 개수, L, R: 질문 범위
    cin >> N >> Q;

    vector<int> A(N);  // 수열 A를 저장할 벡터
    vector<int> S(N);  // 누적 합을 저장할 벡터

    // 수열 A 입력
    for (int i = 0; i < N; i++)
        cin >> A[i];

    // 수열 A를 비내림차순(오름차순)으로 정렬하여 수열 B를 만듦
    sort(A.begin(), A.end());

    // 수열 B의 누적 합 계산
    S[0] = A[0];
    for (int i = 1; i < N; i++)
        S[i] = S[i-1] + A[i];

    // Q개의 질문에 대해 답을 출력
    for (int i = 0; i < Q; i++) {
        cin >> L >> R;
        if (L == 1)
            cout << S[R-1] << '\n';  // L이 1인 경우는 S[R-1] 출력
        else
            cout << S[R-1] - S[L-2] << '\n';  // 그렇지 않은 경우는 구간 합 계산하여 출력
    }

    return 0;
}