[C++] 백준 - 1202번 문제

1202번: 보석 도둑 (acmicpc.net)

1202번: 보석 도둑

 

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)

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

 

출력

---

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

 

 

---

 

생각해 볼 점

---

그리디 문제입니다.

 

이 문제는 우선순위 큐를 이용하는 것이 좋습니다.

 

1. 보석 정보와 가방 정보를 입력을 받습니다.

 

2. 보석 정보와 가방을 무게를 기준으로 오름차순으로 정렬합니다.

 

3. 가방의 무게를 기준으로 가방의 무게보다 작거나 같은 보석의 가치를 PQ(최대 힙)에 push 합니다.

 

4. PQ의 top을 꺼내서 해당하는 보석을 가방에 넣습니다.

 

5. 위 과정을 반복합니다.

 

 

 

 

* 왜 그리디인가?

 

무게가 낮은 가방부터 진행하며,

 

현재 이 가방이 들 수 있는 모든 보석 중 가장 가치가 높은 것을 택하기 때문입니다.

 

코드

---

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int main()
{
    int N, K;
    scanf("%d %d", &N, &K);
            
    pair<int, int> jewels[300000];	//{무게, 가격}
    int bags[300000];			//가방의 무게
    for(int i = 0; i < N; i++)
        scanf("%d %d", &jewels[i].first, &jewels[i].second);
    for(int i = 0; i < K; i++)
        scanf("%d", &bags[i]);

    sort(jewels, jewels + N);	//무게를 우선
    sort(bags, bags + K);

    priority_queue<int> pq;
    int index = 0;
    long long ans = 0;
    
    //무게가 낮은 가방부터 수행
    for(int i = 0; i < K; i++)
    {
    	//가방 무게 이하인 모든 보석의 가치를 pq에 담음
        while(index < N && jewels[index].first <= bags[i])
            pq.push(jewels[index++].second);
        
        if(pq.empty())
            continue;
        
        //가장 높은 가치를 뽑아 더함
        ans += pq.top();
        pq.pop();
    }
    
    printf("%lld", ans);
    return 0;
}

 

그 외

---

정답의 최댓값  : 1000000 * 300000 = 300,000,000,000

 

long long 사용하세요.