[Algorithm]Baekjoon 1202번 : 보석 도둑

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

1202번: 보석 도둑

 
struct Node
{
    int weight;
    int price;
};
 
bool cmp(const Node& a, const Node& b)
{
    return a.weight < b.weight;
}
 
 
int n, k, a, b;
vector<Node> jewels;
vector<int> bags;
priority_queue<int, vector<int>, less<int>> pq;
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> k;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> a >> b;
        jewels.push_back({ a,b });
    }
 
    for (int i = 0; i < k; ++i)
    {
        cin >> a;
        bags.push_back(a);
    }
    
    sort(jewels.begin(), jewels.end(), cmp);
    sort(bags.begin(), bags.end());
    
    int jewelIndex = 0;
    long long answer = 0;
 
    for (int i = 0; i < k; ++i)
    {
        while (jewelIndex < n && bags[i] >= jewels[jewelIndex].weight)
        {
            pq.push(jewels[jewelIndex].price);
            ++jewelIndex;
        }
 
        if (!pq.empty())
        {
            answer += pq.top();
            pq.pop();
        }
    }
 
    cout << answer;
}
 

 

이런 유형을 풀어본적 없다면, n^2밖에 생각이 안날것이다.

나 또한 그랬고, 코테때 망했다.

 

먼저 보석의 가격과 무게를 노드화해서 무게를 기준으로 오름차순 정렬을 한다.

가방도 마찬가지로 무게를 기준으로 오름차순 정렬을 한다.

그리고 보석컨테이너 순회용 인덱스변수를 따로 0으로 초기화선언한다.

 

이후, 가방무게를 담은 컨테이너로 한번 순회하면서 로직을 수행한다.

i번째 가방무게 보다 작은 보석들의 '가격'을 전부 우선순위큐에 담는다.

담을때마다 보석인덱스를 ++해준다.

그다음 우선순위큐의 가장 top값, 즉 가격이 가장 높은것을 answer에 누적시키고 해당 top값을 pop한다.

이 과정을 통해 현재 i번쨰 가방무게에서 가장 비싼 보석을 담는다는게 보장이 된다.

이후에 다시 보석컨테이너를 처음부터 순회하는게 아니라, ++했던 보석인덱스를 그대로 사용해서 하기때문에

n^2이 아니라 N log N 으로 끝난다!

 

몇일만 더 일찍 풀어봤었더라면...