[백준 1202번] 보석도둑 c++ 풀이

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

1202번: 보석 도둑

 

문제 분석

보석이 N개 있고, 해당 보석의 정보인 무게 M, 가격 V가 주어진다.

K개의 가방이 있고, 가방은 각각 C만큼 담을 수 있다.

이때, 가방에 보석을 하나씩만 넣을 수 있다고 할 때, 가져갈 수 있는 최대 보석의 가격을 구하는 문제.

 

dp나 그리디 정도가 떠올랐고,

그리디로 푼다면 보석의 가격이 가장 큰 순서대로, 가방의 무게가 제일 큰 가방에 담아야한다고 생각했다.

 

dp로 풀지 않은 이유는, 한 가방에 보석을 넣은 뒤에 그 다음 다른 가방에 다른 보석을 넣기 때문에, 각각의 프로세스가 서로 영향을 미치지 않는다고 생각했기 때문이다.

---

문제 풀이

 

여기서 몇가지 상황과 조건을 가정해둘 수 있다.

1) 보석은 가장 큰 가격부터 넣는다. 2) 다만, 보석의 무게가 가방의 무게보다 작거나 같아야 들어간다.

3) 가방이 다 찼거나, 보석이 없으면 끝

 

이를 위해 <보석의 무게, 보석의 가격>을 담는 배열과, <가방의 무게>를 담는 배열을 만든다.

 

보석의 무게가 가방의 무게보다 작아 가방에 들어갈 수 있을 때

해당 보석들을 priority queue에 넣어서 가장 큰 보석을 가방에 담을 수 있도록 한다.

 

---

 

핵심은 priority_queue를 언제 쓰냐의 문제였다.

나는 정렬된 보석 관련 리스트에서 최대값을 뽑고, 해당 값을 erase로 지우는 식의 풀이를 생각했었다.

 

<잘못된 코드>

for(auto bags:bagInfo){ // 가방이 큰 것부터 탐색
        if(jwInfo.size()==0){
            break;
        }
        for(i=0;i<jwInfo.size();i++){ // 보석 가치가 높은 것부터 탐색
            if(bags>=jwInfo[i].first){
                totaljw+=jwInfo[i].second;
                jwInfo.erase((jwInfo.begin() + i));
                break; // 해당 보석을 가방에 넣었으면 다음 가방으로
            }
        }
    }

 

<옳은 코드>

int idx=0;
    long long totaljw=0;
    for(auto bags:bagInfo){
        while(idx<jw && bags>=jwInfo[idx].first){
            pq.push(jwInfo[idx].second);
            idx++;
            continue; //왜 continue를 빼도 맞는건지?
        } 
        if(!pq.empty()){
            totaljw+=pq.top();
            pq.pop();
        }
    }

 

하지만 해당 배열에서 최대값을 빼면서 순회하는 것보다, pq에 넣어 가장 큰 값으로 최댓값을 도출하는 것이 더 효율적인듯하다.

그만큼 배열에서 요소를 찾고, 지우는 데 오랜 시간이 걸리는 걸까?

 

 

코드

// deque로 끝값을 빼는 대신, pq로 계속해서 순서를 유지해서 이진탐색으로 해당값을 pop할 수 있는 방법이 있다.
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <queue>
using namespace std;
int jw,bag,i,a,b,c;

vector<pair<int,int>> jwInfo; //보석의 무게, 보석의 가격
vector<int> bagInfo; //가방의 무게
priority_queue<int> pq;
struct compare{
    bool operator()(pair<int,int> &a, pair<int,int> &b){
        return (a.second<b.second);
    }
};
int main(){
    cin>>jw>>bag;
    for(i=0;i<jw;i++){
        cin>>a>>b;
        jwInfo.push_back({a,b});
    }
    for(i=0;i<bag;i++){
        cin>>c;
        bagInfo.push_back(c);
    }
    sort(jwInfo.begin(),jwInfo.end()); //왜 sort를 빼야 맞는건지?
    sort(bagInfo.begin(),bagInfo.end());
    
    int idx=0;
    long long totaljw=0;
    for(auto bags:bagInfo){
        while(idx<jw && bags>=jwInfo[idx].first){
            pq.push(jwInfo[idx].second);
            idx++;
            continue; //왜 continue를 빼도 맞는건지?
        } 
        if(!pq.empty()){
            totaljw+=pq.top();
            pq.pop();
        }
    }
    cout<<totaljw<<endl;
    return 0;
}