[백준] 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)

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

출력

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

 

이 문제는 그렇게 어렵게 보이지는 않지만...

이상하게 풀리지 않았다.

뭐 나 스스로 풀기는 했는데... 메모리초과가 떠서 ㅜㅜ 급하게 다른 분 블로그를 참조하였다.

뭐 그 분꺼를 바탕으로 공부했기 때문에 아마 코드도 비슷하겠지 아마...

 

그러다 우선 순위 큐를 배웠다. 아직은 어떻게 사용하는지는 모르겠지만...

하나 확실한건 우선순위를 지정해서 값을 사용하는 것 같다,

 

 

#include <bits/stdc++.h>
using namespace std;
const int MAX = 300000;

int bag[MAX];
pair<int,int> ruby[MAX];


priority_queue<int> pq;

int main(void) {    
  ios_base::sync_with_stdio(0); 
  cin.tie(0); 

  int  n,k;
  cin >> n >> k;

  for(int i = 0; i<n;i++) {
    cin >> ruby[i].first >> ruby[i].second;
  }

  for(int i = 0; i<k;i++) {
    cin >> bag[i];
  }
  
  sort(ruby,ruby+n);
  sort(bag,bag+k);

  int idx = 0;
  int result = 0;

  for(int i = 0;i<k;i++) {
    while(idx < n && ruby[idx].first <= bag[i]) {
      pq.push(ruby[idx++].second);
    }


    if (!pq.empty()) {
      result += pq.top();
      pq.pop();
    }
  }

  cout << result;

    
}

MAX가 30만인 이유는 그냥 범위가 그렇게 지정되었기 때문이다.

또.. pair를 사용했는데 이건 무게랑 값을 동시에 들고 가야 하기 때문에 이렇게 했다.

뭐... 이걸 맵으로 만들던가.. 아니면   클래스같은걸로 만들어도 되겠지...

 

cin 부분들은 어차피 설정 부분이니 넘어가자.

 

sort하는 이유는 그리디니까.

이 점이 더 간단하잖아...

생각해보면 가장 낮은것을 미리 확인하는게 좋다고 생각했기 때문이다.

 

사실 핵심 부분은 for 과 while문이 같이 있는 부분이다.

 

idx랑 i랑 분리시킨 결정적인 이유는 같이 사용하게 되면

idx가 증가되면 안될때도 i의 영향으로 증가 될 수 있기 때문이다.

 

그러면 값이 나오는데 

문제를 보면 가방에는 최대 무게 가 있다. 그렇기 때문에

보석들의 크기를 각각 비교해줘서 가장 큰 값을 넣어줘야 한다.

하지만 어차피 가장 큰 수는 맨 뒤에 있겠지...

그리고 값을 추가하면 idx를 증가 시켜주면 된다.

 

이제 pq에 값이 존재하면 

 result에 값을 추가해주면 된다. 

 

 

그리고 result에 출력해주면 된다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

bool cmp(pair<int, int>& v_1, pair<int, int> v_2) {
	if (v_1.second > v_2.second) return true;
	else if (v_1.second == v_2.second)
		return v_1.first < v_2.first;
	else
		return false;
}

int main(void) {
	ios::sync_with_stdio;
	cin.tie(0);
	cout.tie(0);
	int n, k;
	cin >> n >> k;
	vector<pair<int, int>>v;
	for (int i = 0; i < n; i++) {
		int m, p;
		cin >> m >> p;
		v.push_back(make_pair(m, p));
	}
	sort(v.begin(), v.end(), cmp);
	multiset<int>s;
	for (int i = 0; i < k; i++) {
		int c;
		cin >> c;
		s.insert(c);
	}
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		auto it = s.lower_bound(v[i].first);
		if (it != s.end()) {
			ans += v[i].second;
			s.erase(it);
		}
	}
	cout << ans << '\n';
	return 0;
}