[BOJ] 1202 : LOPOV

문제 : https://www.acmicpc.net/problem/1202

---

그리디 그리디알고리즘 우선순위큐

[ 문제해석 ]

 N개의 보석과 K개의 가방이 있다. 보석은 크기와 가치가 있고, 가방도 크기가 있다. 가방에는 최대 한 개의 보석만 넣을 수 있고, 가방 크기보다 큰 보석은 넣을 수 없다. 이때, 최대로 얻을 수 있는 가치는 얼마인가 를 구해야되는 문제다.

 

[ 알고리즘풀이 ]

 문제를 그리디하게 접근하면 쉽게 해결 할 수 있다.

 1) 현재 크기가 C인 가방이 있다고 하자. 단순하게 이 가방에 담을 수 있는 보석 중에 가장 가치가 큰 보석을 담는 것이 최대 가치를 얻을 수 있을 것이다.

 하지만, K개의 가방마다 N개의 보석을 순회하며 담을 수 있는 보석 중 가장 가치가 큰 보석을 찾는다면 시간 복잡도가 O(N * K) 가 되어 시간초과에 직면하게 된다. 

 

 2) 현재 크기가 C1인 가방과 C2인 가방이 있고 C2인 가방이 더 크다고 해보자. (C1 < C2)

 그러면 우리는 먼저 C1가방에 담을 수 있는 보석을 구해놓는다면 C2 가방에 담을 수 있는 보석은 C1보다 크기가 크므로 기존에 구해놓은 C1 가방에 담을 수 있는 보석에 추가로 C1 보다 크면서 C2보다 작거나 같은 보석들을 추가로 순회하면 된다. 따라서 보석과 가방이 크기 순으로 sorting 되어있다면 보석과 가방을 한 번 순회하며 문제를 해결 할 수 있다. 즉, 우리는 O(N + K) 로 문제를 해결 할 수 있다.

 

 --> 보석과 가방을 sorting 해놓는다.

 --> 현재 담을 수 있는 보석 중 가장 가치가 큰 보석을 찾아야되므로 priority_queue를 이용한다.

 --> 현재 가방에서 담을 수 있는 보석을 다 priority_queue에 넣고, 가장 가치가 큰 값을 가방에 담는다.

 --> 그 다음 가방에서는 현재까지 순회한 보석 뒤부터 다시 순회를 시작해서 추가로 담을 수 있는 보석을 priority_queue에 담아주고 마찬가지로 가장 가치가 큰 값을 가방에 담는다.

 --> 위 과정을 반복하면 된다.

 

[ 코드구현 C++ ]

#include<iostream>
#include<algorithm>
#include<queue>
 
using namespace std;
 
int N, K;
pair<int, int> jewelries[300000];
int bags[300000];
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> N >> K;
    for (int i = 0; i < N; i++)
        cin >> jewelries[i].first >> jewelries[i].second;
    for (int i = 0; i < K; i++)
        cin >> bags[i];
 
    sort(jewelries, jewelries + N);
    sort(bags, bags + K);
 
 
    priority_queue<int> pq;
    int jewelry = 0;
    long long ans = 0;
 
    for (int i = 0; i < K; i++) {
        for (int j = jewelry; j < N; j++) {
            if (jewelries[j].first > bags[i]) break; // 지금 가방에 못 넣는 보석!
            pq.push({ jewelries[j].second });
            jewelry++;
        }
        if (!pq.empty()) {
            ans += pq.top();
            pq.pop();
        }
    }
    cout << ans << '\n';
}

[ github ]

github.com/travelbeeee/ProblemSolving/blob/master/BOJ/BOJ1202.cpp

travelbeeee/ProblemSolving

---