[백준/C++] 1202번: 보석 도둑(G2)

 

문제

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

1202번: 보석 도둑

 

사용한 알고리즘

• 2022.02.02 - [PS/Algorithm] - [알고리즘 개념정리] 7. 이분탐색/분할정복

     -> lower_bound

• multiset

 

 

풀이

max heap을 이용하여 보석을 가격이 높은 순으로 top에 오도록 한다.
보석을 가방에 넣을 때는 보석을 넣을 수 있는 가장 작은 가방을 사용한다.
이때, lower_bound를 사용해주었다.

가방 용량을 벡터에 담아두고, 사용한 가방은 vector.erase()하는 방식으로 풀었었는데
시간초과가 났다. (제출 코드)

질문 글을 참고하다가 O(n)인 v.erase() 때문이라는 것을 알게되었고, 벡터를 multiset으로 바꾸었다.
multiset의 erase는 O(logn)이다.

multiset 사용법은 아래 링크에 잘 나와있다.
https://www.cplusplus.com/reference/set/multiset/lower_bound/

multiset::lower_bound - C++ Reference

https://blockdmask.tistory.com/80

[C++] multiset container 정리 및 사용법

 

 

 

소스코드

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
/*
 * 보석 가격 높은순
 * 가방 작은거부터 시도-> 이분탐색
 * 1 65
 * 5 23
 * 3 99
 * 10
 * 2
 */
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    priority_queue<pair<int,int>> pq; //보석담기
    multiset<int> vt; //가방
    ll n,k,ans=0; cin>>n>>k;
    for(int i=0; i<n; i++){
        int m,v; cin>>m>>v;
        pq.push({v,m}); //가격, 무게
    }
    for(int i=0; i<k; i++){
        int c; cin>>c;
        vt.insert(c);
    }

    while(!vt.empty()){
        if(pq.empty()) break; //보석보다 가방이 많다면 (보석 다 담으면) 종료
        pair<int,int> tmp = pq.top(); pq.pop();
        multiset<int>::iterator low = vt.lower_bound(tmp.second);
        if(low==vt.end()) continue; //모든가방이 보석보다 작다면 못담음
        else vt.erase(low); //보석 담은 가방은 제거
        ans+=tmp.first;
    }
    cout<<ans;
    return 0;
}