[백준 1202] 보석 도둑

백준 1202 보석 도둑 - 문제 링크

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

풀이

문제가 겁나 간단하다. 근데 이게 골드 2라고? 처음에 그렇게 생각헀다.
그냥 가방이랑 보석을 정렬하고, 가장 비싼 보석부터 최대한 무게가 낮은 가방에 넣도록 알고리즘을 짰다.

무식하게 for문을 돌려서 짜니까 시간 초과가 되었다.

자세히 보면 N,K는 최대 30만까지 입력을 받는데, 이중 for문을 돌려버리니 시간복잡도가 O(NK) 여서 시간초과가 나는 것.

그래서 게시판을 뒤져보니 시간 복잡도를 해결하기 위한 두가지 방법이 있었다.

1. Memset 과 Lower_bound 를 이용하는 방법

2. Priority Queue를 이용하는 방법

처음에는 Vector를 Memset으로 바꿔서 해보려고 했는데, set 자료형식에 대한 이해가 부족해 정렬 후 lower_bound를 사용하는 부분에서 막혔다.

그래서 자주 쓰던 우선순위 큐를 이용하는 방법을 사용했다.
풀이 방식은 이러하다.

1. 보석이랑 가방을 무게가 낮은 순으로 정렬한다.(오름차순)

2. 가장 무게가 가벼운 가방에서부터 보석의 무게랑 비교를 하고, 보석이 들어갈 수 있으면 우선순위 큐에 푸시한다. 푸시가 모두 끝나면, 큐가 비어있지 않으면 큐의 top을 더하고 pop 해준다.

3. 가방을 다 비교할 때 까지 반복한다.(물론 모든 보석의 탐색이 먼저 끝나면 자동으로 끝난다.)

코드는 더 간단하다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    vector<pair<int,int>> vec;
    priority_queue<int> pq;
    int N,K;
    cin >> N >> K;
    int m[N];
    int v[N];
    for(int i = 0; i<N; i++) {
        cin >> m[i] >> v[i];
        vec.push_back({m[i], v[i]});
    }
    int c[K];
    for(int i = 0; i<K; i++)
        cin >> c[i];

    sort(vec.begin(),vec.end());
    sort(c,c+K);

    long long answer = 0 ;
    int j = 0;
    for(int i = 0; i<K; i++){
        while(vec[j].first <= c[i] && j < N){
            pq.push(vec[j].second);
            j++;
        }
        if(!pq.empty())
        {
            answer += pq.top();
            pq.pop();
        }
    }

    cout << answer;

}

아무리 봐도 알고리즘 자체는 골드 2 수준은 아닌거 같은데 시간 초과 때문에 한번 더 생각을 해야해서 골드2가 된 것 같다.