[BOJ] 1202번 - 보석 도둑

백준 1202번 - 보석 도둑

시간제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	17493	3999	2809	22.281%

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

---

예제 입력 1

3 2
1 65
5 23
2 99
10
2

예제 출력 1

164

출처

www.acmicpc.net/problem/1202

1202번: 보석 도둑

알고리즘 분류

• 자료 구조
• 그리디 알고리즘
• 우선순위 큐

접근 방법

처음 문제를 읽었을 때, "가방에는 최대 한 개의 보석만 넣을 수 있다." 라는 문장이 눈에 들어왔다.

해당 조건이 있기 때문에, 항상 제일 가벼운 가방 부터 고려하였을 때, 해당 가방이 담을 수 있는 최대가치의 보석을 선택하는 전략으로 최적해를 구할 수 있다. 증명은 귀류법으로 쉽게 확인할 수 있으므로 생략하겠다.

 

자 그러면, 가방의 무게 ( ${C_i}$ ) 보다 낮은 무게를 가진 보석 중 최대 가치의 보석을 선택하기 위해서는 어떤 방식으로 접근해야할까?

단순하게, Brute-Force 방식으로 접근한다면, ${O(N^2)}$ 가 되므로 TLE 일 것이다.. 

 

두번째로 생각해 볼 수 있는 방법은 "보석"을 기준으로 {key : 무게, value : 가치} 로 오름차순 정렬을 하고 lower_bound 를 통해서 구한 target까지 검사하여 최대 가치를 찾는 방법이 있겠다. 하지만, 이것 또한 최악의 경우 ${O(N^2)}$가 되므로 TLE이다.

 

마지막으로, bag의 Weight를 Binary Search Tree에 넣어둔다. 이를 위해서, Set 기반의 stl 중 중복된 값을 허용하는 multiset을 이용한다.

이 후, 가치가 가장 큰 보석부터 순차적으로 확인해주면서 해당 보석을 담을 수 있는 가방이 있는 지 확인하고, 해당 하는 가방이 없으면 해당 보석을 담을 수 있는 가방이 없으므로 다음 보석을 고려해주고 그렇지 않다면, 해당하는 가방 중 가장 가벼운 가방을 제거해준다. Set은 BST기반이므로 노드를 삭제하는데 걸리는 시간은 log타임이므로 충분히 문제를 해결 할 수 있다.

전체의 시간복잡도는 ${O(NlogN)}$ 이 된다. 

 

+ 추가적으로, Set의 멤버함수 lower_bound와 STL 함수인 lower_bound 의 차이점을 기술한 좋은 자료를 아래에 태그해 놓았다.

www.geeksforgeeks.org/difference-between-stdsetlower_bound-and-stdlower_bound-in-c/

Difference between std::set::lower_bound and std::lower_bound in C++ - GeeksforGeeks

stackoverflow.com/questions/31821951/c-difference-between-stdlower-bound-and-stdsetlower-bound

C++ Difference between std::lower_bound and std::set::lower_bound?

소스 코드

#include <bits/stdc++.h>
using namespace std;
int N, K;
int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    cin >> N >> K;

    // 제일 가벼운 가방 부터 담을 수 있는 최대 가치의 보석을 선택하는 전략
    // 제일 비싼 보석부터 하나씩 보면서, 해당 보석을 담을 수 있는 가방이 존재하는 지 확인
    // 존재한다면, 해당 가방을 erase 한다. * 시간 복잡도 개선 위해서 어떤 자료구조 ?

    vector<pair<int,int>> J(N);
    for(int i=0; i<N; i++){
        int M, V;
        cin >> M >> V ;
        J[i].first = V, J[i].second = M;
    }
    sort(J.begin(), J.end(), greater<pair<int,int>>());

    multiset<int> bagWeight;
    for(int i=0; i<K; i++){
        int W;
        cin >> W ;
        bagWeight.insert(W);
    }

    long long answer = 0;
    for(int i=0; i<N; i++){
        auto target = bagWeight.lower_bound(J[i].second);
        if( target == bagWeight.end() )
            continue;
        answer += J[i].first;
        bagWeight.erase(target);
    }

    cout << answer;
    return 0;
}