[Codeforces] Promo

https://codeforces.com/contest/1697/problem/B

Problem - B - Codeforces

아쉽게도 시간 초과가 발생해서 틀린 문제이다.

 

시간 초과가 발생한 풀이법

i개의 아이템을 가격 내림차순으로 정렬한 후, $y$는 $x$개의 아이템들 중 가장 저렴한 아이템의 개수이므로 $p_1...p_x$ 총 $x$개 중에서 뒤에서부터 $y$개를 방문하며 합을 구하도록 하였다.

 

그런데 시간 초과가 발생하다 이번에는 x 구간 내에서 y 구간과 비 y 구간의 크기를 비교하여 크지 않은 곳의 합을 구하여 최종적으로 y구간의 합을 구하는 방법을 택했다. 그런데 이번에도 시간 초과 발생!!........ㅠㅠ

 

시간 초과가 발생하지 않은 방법

도저히 방법이 떠오르지 않아서 대회가 끝난 후에서야 풀었다..

바로 매 쿼리마다 구간합을 구하는 것이 아니라 정렬 후 구간합(prefix sum)을 미리 구해놓으면 많은 수의 쿼리도 빠르게 할 수 있었다.

아무래도 이전에 자주 풀었던 프로그래머스에서는 테스트케이스와 같은 다수의 쿼리를 수행하는 것이 아니라 일회성의 결과만 내놓으면 됐기 때문에 이런 방법을 활용하는 것을 바로 떠올리지 못했던 것 같다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    int n, q;
    cin >> n >> q;
    vector<int> items(n);
    vector<long long> pre_sum(n);
    for(int i = 0;i < n;i++) {
        cin >> items[i];
    }
    
    sort(items.begin(), items.end(), greater<int>());
    pre_sum[0] = items[0];
    for(int i = 1;i < n;i++) {
        pre_sum[i] = pre_sum[i - 1] + items[i];
    }
    for(int i = 0;i < q;i++) {
        int x, y;
        cin >> x >> y;
        if(x == y) {
            cout << pre_sum[x - 1] << '\n';
        }
        else {
            cout << pre_sum[x - 1] - pre_sum[x - y - 1] <<'\n';
        }
    }
}

여기서 x와 y가 동일한 경우의 시작점을 잡을 때 주의해야 한다. x와 y가 동일하다면 $x - y - 1$이 음수가 되어 메모리를 벗어나는 일이 발생하기 때문이다. 따라서 예외처리를 적절히 해주어야 한다.