[백준/C++] 1202번 보석 도둑

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

1202번: 보석 도둑

이 문제는 입력의 범위가 좀 크기 때문에 그냥 O(N^2)으로 탐색하게 되면 시간초과가 발생할 수 있는 가능성이 존재한다.

그러면 어떻게 푸냐? 그리디 알고리즘을 이용하자!

​

1. 우선 입력을 받고,

2. 보석의 정보와 가방의 정보들을 오름차순(작은 것부터)으로 정렬해준다. 정렬할 때는 greater<>나 less<>를 사용해도 되지만, 비교함수를 이용할 수도 있다. return되는 값이 false일 때 swap되므로 유의하자!

(우선 순위 큐에서는 return이 true일 때 swap되는 것 같다.)

​

3. 그 다음 가방의 개수만큼 for문을 반복하는데, 2중 for문을 사용하지 않고 따로 인덱스를 하나 더 둔다.

이게 바로 이 문제의 그리디한 풀이 방법이다!

​

-> 일단, 보석들과 가방들의 정보를 오름차순으로 정렬했다고 치자. 그리고 제일 작은 가방부터 보석을 넣을 수 있을지 없을지 탐색한다. 만약 보석을 넣을 수 있다면, 보석의 가격을 큐에 삽입해주고 인덱스를 1 증가 시킨다. 보석을 넣을 수 없다면 앞서 정렬해준 것 때문에 다음 가방으로 넘어갈 것이다. 다음 가방으로 넘어가기 전에, 큐에 삽입한 보석들 중 제일 비싼 것을 누적해서 더해준다. 그리고 해당 보석을 큐에서 삭제한다!

이렇게 하면 왜 그리디 할까? "작은 가방에 들어갈 수 있는 것은 굳이 또 탐색하지 않아도 큰 가방에 들어갈 수 있기 때문이다!"

​

예제 입력 2를 예시로 들어보자.

1 65

5 23

2 99

10

2

위와 같이 주어졌다고 했을 때, 입력을 오름차순으로 정렬하면,

1 65

2 99

5 23

2

10 과 같은 형태가 될 것이다!

​

그러면 사이즈 2인 가방에 대해서 먼저 탐색을 시작하는데, 무게가 1과 2인 보석은 모두 담을 수 있으므로 큐에 65와 99를 삽입할 것이다. (현재 큐 : 99 65) (1 65 와 2 99에 대해 성공적으로 담았으므로 인덱스 J는 2번 증가)

그리고 5는 담을 수 없으므로, 사이즈가 10인 가방에 대해 탐색을 시작한다. (현재 인덱스 J가 가리키고 있는 것은 5 23 일 것이다)

현재 인덱스가 가리키는 보석(5 23)을 담을 수 있으므로 큐에 23을 삽입해준다. (현재 큐 : 65 23)

가방 하나에 대해서 탐색이 끝날 때 마다 최댓값을 누적하므로, 정답은 결국 99 + 65가 될 것이다!

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#include<string>
#include<cctype>
#include<cmath>

using namespace std;

long long n,k,m,v,c,sum;
priority_queue<long long> pq;
vector<pair<long long,long long>> jewelry;
vector<long long> bag;

bool cmp(pair<long long, long long> a, pair<long long, long long> b){
    if(a.first==b.first) return a.second > b.second;
    return a.first < b.first;
}

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

    cin >> n >> k;

    for(long long i=0; i<n;i++){
        cin >> m >> v;
        jewelry.push_back({m,v});
    }
    for(long long i=0; i<k;i++){
        cin >> c;
        bag.push_back(c);
    }
    sort(jewelry.begin(),jewelry.end(),cmp);
    sort(bag.begin(),bag.end());

    long long j=0;
    for(long long i=0; i< k;i++){
        while(j<n && jewelry[j].first <= bag[i]) {
            pq.push(jewelry[j].second);
            j++;
        }
        if (!pq.empty()){
            sum += pq.top(); pq.pop();
        }
    }

    cout << sum;
    return 0;
}