[백준/Baekjoon] 1202 보석 도둑 C++ :: Greedy

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

1202번: 보석 도둑

---

1. Logic

multiset 해설

1. 우선순위큐에 보석의 가치와 무게 순으로 넣는다.

2. 가방의 무게를 입력받아 multiset으로 넣는다.

3. multiset은 오름차순으로 정리되기 때문에 lower bound(O(logN))을 활용하여 보석의 무게와 같거나 더 큰 가방을 찾는다

 

vector 해설

1. 보석과 가방을 벡터에 입력 받아준 후 오름차순으로 정렬한다.

2. 보석의 무게와 가방의 용량을 비교하여 가방에 들어갈 수 있는 무게를 가진 보석들만 우선순위 큐에 넣어준다.

3. 그 중에서 가장 높은 가치를 가진 보석의 값만 더해주고 pq에서 pop()

 

처음에는 벡터와 우선순위 큐에 값을 넣고 모두 순회하며 그리디한 방식으로 접근을 했지만 시간초과가 났다. 그래서 vector의 순회가 문제인 것 같아 시간복잡도가 O(logN)을 가지는 자료구조인 Multiset 을 활용하여 풀었다. multiset 또한 iterator을 사용하여 처음부터 끝까지 돌며 확인했지만 또 시간초과가 떠서 값을 찾는 방식을 multiset의 O(logN)의 이진탐색을 활용한 multiset의 lower_bound를 사용하니 정답 처리가 됐다. 

자료구조의 문제인줄 알고 다시한번 vector의 lower_bound로 구현해봤더니 시간초과가 떴다.

결론적으로 자료구조와 lower_bound 둘다 잘 맞아 떨어져야 하는 문제인 것같다.

 

코드는 multiset 순회, multiset - lower_bound, vector 활용, vector - lower_bound 4가지 버전 다 올려놓을 것이다.

 

 

---

2. Code

multiset - lower_bound 풀이 - 정답

#include<bits/stdc++.h>
#include <queue>
#include <set>

using namespace std;

priority_queue<pair<int, int>> pq;
multiset<int> bag;

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

    long long n, k;
    long long answer = 0;

    cin >> n >> k;

    for(int i = 0; i < n; i++) {
        int weight, value;
        cin >> weight >> value;
        pq.push({value, weight});
    }

    for(int i = 0; i < k; i++) {
        int size;
        cin >> size;
        bag.insert(size);
    }
    
    
    while(!bag.empty()) {
        if(pq.empty()) break;
        //multiset<int>::iterator iter = bag.lower_bound(pq.top().second);
        multiset<int>::iterator iter;
        bool check = false;
        for(iter = bag.begin(); iter != bag.end(); iter++){
            if(*iter >= pq.top().second) {
                check = true;
                bag.erase(iter);
                answer += pq.top().first;
                pq.pop();
                break;
            }
        }
        if(!check) {
            pq.pop();
        }
    }

    cout << answer;
}

multiset 순회 - 시간 초과

 

#include<bits/stdc++.h>
#include <queue>
#include <set>

using namespace std;

priority_queue<pair<int, int>> pq;
multiset<int> bag;

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

    long long n, k;
    long long answer = 0;

    cin >> n >> k;

    for(int i = 0; i < n; i++) {
        int weight, value;
        cin >> weight >> value;
        pq.push({value, weight});
    }

    for(int i = 0; i < k; i++) {
        int size;
        cin >> size;
        bag.insert(size);
    }
    
    
    while(!bag.empty()) {
        if(pq.empty()) break;
        //multiset<int>::iterator iter = bag.lower_bound(pq.top().second);
        multiset<int>::iterator iter;
        bool check = false;
        for(iter = bag.begin(); iter != bag.end(); iter++){
            if(*iter >= pq.top().second) {
                check = true;
                bag.erase(iter);
                answer += pq.top().first;
                pq.pop();
                break;
            }
        }
        if(!check) {
            pq.pop();
        }
    }

    cout << answer;
}

벡터를 활용한 풀이 - 정답

#include<bits/stdc++.h>
#include <queue>

using namespace std;

int n, k;

vector<int> bag;
vector<pair<int, int>> jems;
priority_queue<int> pq;

long long solve() {
    int idx = 0;
    long long sum = 0;

    for(int i = 0; i < k; i++) {
        // 가방에 들어갈 수 있는 무게를 가진 보석들을 전부 넣기
        while(idx < n && bag[i] >= jems[idx].first) {
            pq.push(jems[idx].second);
            idx++;
        }
        if(!pq.empty()) {
            sum += pq.top();
            pq.pop();
        }
    }
    return sum;
}

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

    cin >> n >> k;

    for(int i = 0; i < n; i++) {
        int weight, value;
        cin >> weight >> value;

        jems.push_back({weight, value});
    }

    for(int i = 0; i < k; i++) {
        int a;
        cin >> a;
        bag.push_back(a);
    }

    sort(jems.begin(), jems.end());
    sort(bag.begin(), bag.end());

    cout << solve();
}

vector - lower_bound - 시간 초과

 

#include<bits/stdc++.h>
#include <queue>
#include <set>

using namespace std;

priority_queue<pair<int, int>> pq;
vector<int> bag;

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

    long long n, k;
    long long answer = 0;

    cin >> n >> k;

    for(int i = 0; i < n; i++) {
        int weight, value;
        cin >> weight >> value;
        pq.push({value, weight});
    }

    for(int i = 0; i < k; i++) {
        int size;
        cin >> size;
        bag.push_back(size);
    }
    
    sort(bag.begin(), bag.end());
    
    while(!bag.empty()) {
        if(pq.empty()) break;
        vector<int>::iterator iter = lower_bound(bag.begin(), bag.end(), pq.top().second);
        if(iter == bag.end()) {
            pq.pop();
            continue;
        }
        else {
            bag.erase(iter);
            answer += pq.top().first;
            pq.pop();
        }
    }

    cout << answer;
}

---

3. Feedback

처음에 시간초과를 받은 후 다른 자료구조를 생각해보다가 나름 빠른시간안에 multiset을 생각해낸 것 만으로도 만족스러웠다. 그리고 multiset과 vector의 iterator을 사용할 줄 몰라 엄청 찾아보면서 풀었다. 결국 구글링을 해보면서 생각해낸 4가지 풀이 모두 정답을 받진 못했지만 이건 문제의 조건때문이기 때문에 구현을 완료해서 굉장히 뿌듯햇다. 그리고 처음으로 집요하게 파고들어 자료구조, STL등 깊게 찾아보며 풀이한 첫번째 문제인 것 같다. 알고리즘 공부에 대해 느낀점을 만들어 준 문제인 것 같아 쉽게 안잊힐 것 같다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐