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 복사

3 2

1 65

5 23

2 99

10

2

예제 출력 1 복사

164

---

 

simjy954님의 multiset을 이용한 풀이

#include <iostream> // BOJ 1202번: 보석 도둑
#include <algorithm> // to use sort
//#include <functional> // to use greater
#include <vector>
#include <set> // to use set, lower_bound
using namespace std;

//vector<int> arr_v; // 보석의 가격 저장
//vector<int> arr_m; // 보석의 무게 저장
vector<pair<int, int>> arr;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	// N은 보석점의 보석의 개수
	// K는 상덕이의 가방 수
	int N, K; cin >> N >> K; // 보석 개수랑 가방 수 최대 300,000
	int *M, *V, *C;

	M = new int[N]; // 보석의 무게와 가격 모두
	V = new int[N]; // 보석의 개수 만큼 입력 가능

	// 가방에 담을 수 있는 최대 무게는 상덕이의 가방 수 만큼 입력 가능
	C = new int[K];

	for (int i = 0; i < N; i++) { // N개의 줄 동안 입력
		// M은 각 보석의 무게, V는 각 보석의 가격
		cin >> M[i] >> V[i]; // 보석의 무게와 가격은 최대 1,000,000
		// 정렬에 쓰려고 각 vector에 저장
		// arr_v.push_back(V[i]);
		// arr_m.push_back(M[i]);
		arr.push_back(make_pair(V[i], M[i]));
	}
	// set 컨테이너 사용: 가방에 담을 수 있는 최대 무게를 담음
	//set<int> s;
	// set은 중복키를 허용X, multiset은 중복키를 허용O
	// 같은 무게의 가방이 여러개 들어올 수 있어서 multiset으로 변경
	multiset<int> s;

	for (int j = 0; j < K; j++) { // K개의 줄 동안 입력
		cin >> C[j];
		s.insert(C[j]);
	}
	//sort(arr.begin(), arr.end()); // 오름차순
	//reverse(arr.begin(), arr.end()); // 뒤집어서 내림차순-> greater가 pair 안먹어서 변경
	sort(arr.rbegin(), arr.rend());
	//sort(arr_v.begin(), arr_v.end(), greater<int>()); // 보석 가격 큰 순서대로 내림차순 정렬
	//sort(arr_m.begin(), arr_m.end()); // 보석 무게 기준 오름차순 정렬
	//sort(C, C + K); // 가방에 담을 수 있는 무게 오름차순 정렬 -> set 넣어서 필요X

	long long int max = 0; // 가방 속에 넣을 수 있는 최대 보석 가격
	multiset<int>::iterator iter; // lower_bound 반환형과 맞는 자료형을 가지는 iter 변수

	for (int i = 0; i < N; i++) {
		// lower_bound로 무게 넘지 않으면서 가장 큰 값을 찾음
		// lower_bound는 찾는 값 이상, upper_bound는 찾는 값 초과를 반환
		// 찾는 값이 범위내에 없다면 end()를 반환한다고 한다 -> error 났다.
		// 그래서 key 값을 실수하지 말고 잘 주어야한다.
		// 사용법을 찾아보다 발견: lower_bound가 set에 내장되어있는 것을 써야-> O(nlogn)
		// 만약 내장된 것이 아닌 lower_bound를 사용하면-> O(n) -> 이 문제에서 불가능
		iter = s.lower_bound(arr[i].second);
		if (!s.empty() && iter != s.end()) { // 찾는 값이 범위 내에 있으면
			s.erase(iter); // 무게 범위에서 확인되어 지운다.
			max += arr[i].first; // 해당하는 보석 가격을 더해준다.
		}
	}
	cout << max; // 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값 출력
	return 0;

 

/* 보석 도독 */
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define MAX 300001
using namespace std;

int n, k;
long long sum;
vector<int> bag; // 가방목록
vector<pair<int, int>> jewel; // 보석 목록
bool visited[MAX]; // 훔쳤나 안 훔쳤나 체크 목록

int main() {
	ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
	
	cin >> n >> k;
	for(int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		jewel.push_back(make_pair(a, b));
	}
	for(int i = 0; i < k; i++) {
		int input;
		cin >> input;
		bag.push_back(input);
	}
	sort(jewel.begin(), jewel.end());
	sort(bag.begin(), bag.end());
	
	int idx = 0;
	priority_queue<int> pq;
	for(int i = 0; i < bag.size(); i++) {
		while(idx < n && jewel[idx].first <= bag[i]) {
			pq.push(jewel[idx++].second);
		}
		
		if(!pq.empty()) {
			sum += pq.top();
			pq.pop();
		}
	}
	cout << sum << '\n';
	
	return 0;
}