[백준] 1202번 보석도둑 -C++

문제

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

상덕이가 털 보석점에는 보석이 총 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)

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

출력

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

문제 요약:

가방에 담을 수 있는 최대 무게를 넘기지 않고 보석을 담아서 보석 가격의 합의 최대 구하기

생각할 점:

• 가방에는 한 개의 보석만 넣을 수 있다.
• 보석 가격 합의 최대가 되려면?
  • 보석을 무게 기준 오름차순, 가방 제한 무게 벡터도 오름차순
  • 최대 무게가 작은 가방부터 하나씩 반복하면서
  • 가방에 들어갈 수 있는 보석들의 가치를 저장한 벡터 bag에 무게가 가방의 용량을 넘지 않는 보석들의 인덱스 저장
  • bag에 들어갈 수 있는 보석이 있다면 보석들의 가치를 기준으로 내림차순 정렬해서 가장 가치가 큰 것만 최대 가격을 반환할 답 answer에 추가하고 맨 앞의 가장 가격이 높은 보석 인덱스를 지워준다.
  • 그 다음 가방 반복

처음에는 우선순위 큐를 사용한다는 생각을 못해서 bag 벡터에 매번 가격 순으로 내림차순 정렬을 해서 가장 가격이 높은 보석을 찾는 방법을 사용했다. 하지만 우선순위 큐를 사용한다면 큐에 데이터를 넣을 때마다 알아서 내림차순 정렬로 가장 가격이 높은 순으로 정렬이 되기 때문에 시간 복잡도 측면에서 훨씬 개선할 수 있다.
우선순위 큐-C++

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

int main(){
    int N, K;
    cin >> N >> K;

    vector<pair<int,int>> jewel(N);
    for (int i = 0; i < N; i++) {
        //무게, 가치
        cin >> jewel[i].first >> jewel[i].second;
    }

    vector<int> capacity(K);
    for(int i = 0; i < K; i++){
        cin >> capacity[i];
    }

    sort(jewel.begin(), jewel.end());
    sort(capacity.begin(),capacity.end());

    long long answer = 0;
    int index= 0;
    priority_queue<int> bag;

    for (int i = 0; i < K; i++) {
        while (index < N && jewel[index].first <= capacity[i]) {
            bag.push(jewel[index].second);
            index++;
        }

         if(!bag.empty()){
            answer += bag.top();
            bag.pop();
            
        }

    }

    cout << answer << endl;
}

풀이

🌟 초기화

• 보석의 수 N, 가방의 수 K로 입력받아
• 보석의 수 만큼 보석의 무게와 가격을 쌍으로 입력받는 벡터 jewel
• 가방의 최대 무게를 입력받아 저장하는 벡터 capacity 를 생성한다.

int N, K;
    cin >> N >> K;

    vector<pair<int,int>> jewel(N);
    for (int i = 0; i < N; i++) {
        //무게, 가치
        cin >> jewel[i].first >> jewel[i].second;
    }

    vector<int> capacity(K);
    for(int i = 0; i < K; i++){
        cin >> capacity[i];
    }

🌟 정렬

• 보석들의 무게를 기준으로 오름차순 정렬하고
• 가방의 최대 무게를 기준으로 오름차순 정렬한다.

sort(jewel.begin(), jewel.end());
sort(capacity.begin(),capacity.end());

🌟 로직

• 가방에 들어갈 수 있는 보석들의 가격을 저장할 우선순위 큐 bag 생성
• 가방 하나마다 들어갈 수 있는 보석의 무게를 조건문으로 비교해 해당하는 인덱스의 보석의 가격을 bag 큐에 추가한다.
• 한 가방에 들어갈 수 있는 보석을 모두 찾아 가방이 비어있지 않다면 우선순위 큐의 가장 top의 값( 가장 가격이 높은 보석) 을 answer에 더해주고 큐에서 해당값을 삭제한다.

long long answer = 0;
    int index= 0;
    priority_queue<int> bag;

    for (int i = 0; i < K; i++) {
        while (index < N && jewel[index].first <= capacity[i]) {
            bag.push(jewel[index].second);
            index++;
        }

         if(!bag.empty()){
            answer += bag.top();
            bag.pop();
            
        }

    }