백준) 1202 보석 도둑

1202. 보석 도둑

문제

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

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

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

입력

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

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

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

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

출력

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

예제 입력 

3 2
1 65
5 23
2 99
10
2

예제 출력 

164

1. 접근

가방들에 최대한 비싼 보석들을 담아야 한다.

가방엔 보석을 하나만 넣을 수 있으므로 가장 비싼 보석을 넣어야한다.

가방마다의 부분문제로 이루어진 그리디 문제.

2. 풀이

탐욕적인 방법 : 가장 무게제한이 낮은 가방(A1)부터 최대한 비싼 보석을 넣는 방법을 쓰기로 한다.

정당성을 증명하기 위해, A1에 들어가는 보석들 중에 가장 비싼 보석(B)을 고르지 않는 방법이 실은 정답이라고 가정해보자.(귀류법)

무게 순으로 A1, A2, A3, ... 인 가방들의 특징은, A1이 담을 수 있는 보석은 당연히 A2도 담을 수 있다는 것이다.

따라서 직관적으로 가장 큰 가방만이 담을 수 있는 보석들이 있을 것이고, 최적해를 위해선 가장 비싼 보석을 골라야한다.

같은 의미로 A1도 A1이 담을 수 있는 가장 비싼 보석을 골라야한다. A1의 선택은 뒤의 선택에 영향을 미치지 않는다.

남은 부분문제도 첫 부분문제와 동치인 문제들이다.

3. 코드

#include <stdio.h>
#include <algorithm>
#include <queue>
using namespace std;
 
typedef pair<int, int> p;
p jew[300000];
int bag[300000];
int n, k, m, v, c, i, j;
 
int main() {
    scanf("%d %d", &n, &k);
    for (i = 0; i < n; ++i) {
        scanf("%d %d", &jew[i].first, &jew[i].second);
    }
    for (i = 0; i < k; ++i)
        scanf("%d", &bag[i]);
 
    sort(jew, jew + n);
    sort(bag, bag + k);
 
    long long sum = 0;
    priority_queue<int> pq;
    for (i = 0, j = 0; i < k; ++i) {
        while (j < n && jew[j].first <= bag[i])
            pq.push(jew[j++].second);
        
        if (!pq.empty()) {
            sum += pq.top();
            pq.pop();
        }
    }
    printf("%lld", sum);
    return 0;
}

4. 후기

컵라면 문제 (http://js1jj2sk3.tistory.com/12)와 많이 닮아 있는 문제다.

문제와 관련된 두 가지 조건(데드라인+컵라면 수 / 무게 제한 + 비싼 보석) 중에

원하는 정답조건(최대한 많은 컵라면 / 최대한 비싼 보석들의 합) 말고 다른 조건(데드라인 / 무게 제한) 순으로 정렬하고,

조건에 맞는 모든 경우를 수집한 다음(우선순위 큐에 저장한다음), 최적해를 고른다.