보석 도둑 (feat. 백준, 1202번)

보석 도둑
https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    ios::sync_with_stdio(false), cin.tie(NULL);
    register int N, K;
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> jewel;  // 보석 무게 오름차순
    priority_queue<int, vector<int>, greater<int>> bag;     // 가방 무게 오름차순
    priority_queue<int> jewel_cost; // 보석 가격 내림차순
    cin >> N >> K;
    for(register int n = 0, m, v; n < N; ++n)
        cin >> m >> v, jewel.push(make_pair(m, v));
    for(register int k = 0, c; k < K; ++k)
        cin >> c, bag.push(c);    // 가방무게 오름차순
    register long long ans = 0;
    while(!bag.empty()){
        auto c = bag.top(); bag.pop();  // 가방 무게 (가벼운거부터)
        while(!jewel.empty()){
            auto p = jewel.top();     // 보석 무게 (가벼운거부터)
            if(p.first > c) // 보석 무게가 가방 무게보다 무거우면 종료
                break;
            jewel_cost.push(p.second);  // 보석 가격만 수집
            jewel.pop();    // 사용했으니 버림
        }
        if(!jewel_cost.empty()){
            ans += jewel_cost.top(); jewel_cost.pop();    // 제일 비싼거 꺼냄
        }
    }
    cout << ans;
    return 0;
}
// *&)*@*

 

1. 입력받은 보석 정보와 가방은 무게를 기준으로 오름차순 해줍니다. (가벼운 보석부터, 가벼운 가방부터)
2. 가방의 무게보다 작거나 같은 보석의 가격을 모아줍니다. 모을때는 입력받았던 보석 정보는 삭제시켜줍니다. (다음 가방에서 다시 탐색하지 않기 위해서)
3. 모여진 보석 가격들 중 가장 비싼 보석이 해당 가방보다 무게가 작거나 같으면서 가장 비싼 보석입니다.
4. 계속 틀리길래 힌트를 보니 정답은 long long 자료형이어야 한다고 합니다.