백준[1202] 보석 도둑

아이디어

• 그리디 알고리즘을 사용할 줄 안다
• multiset을 사용할 줄 안다
• lower_bound를 사용할 줄 안다

풀이

1. multiset을 이용하여 bag을 저장한다
2. 보석의 정보를 vector에 저장하고, sort를 통해 정렬해준다
3. 보석의 value를 큰값부터 조사하되(본인은 음수를 이용하여 저장), bag에서 lower_bound를 통해 bag의 weight의 iterator를 구한다
4. 만약 end()가 아닐 경우 찾은 경우 이니, 해당 value를 더해주고, bag에서 사용한 가방을 삭제해준다.

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <string>
#include <math.h>
#include <set>
#define ll long long

using namespace std;

multiset<int> bag;
vector<pair<int, int>> crystal;

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

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

	for (int i = 0; i < n; i++) {
		int m,v; // m == weight, v == cost
		cin >> m >> v;
		crystal.push_back({ -v,m });
	}

	for (int i = 0; i < k; i++) {
		int c;
		cin >> c;
		bag.insert(c);
	}

	sort(crystal.begin(), crystal.end());

	ll answer = 0;

	for (auto iter = crystal.begin(); iter != crystal.end(); iter++) {

		if (bag.size() == 0) break;

		int crystal_value = -((*iter).first);
		int crystal_weight = (*iter).second;

		auto bag_iter = bag.lower_bound(crystal_weight);

		if (bag_iter != bag.end()) {
			answer += crystal_value;
			bag.erase(bag_iter);
		}

	}

	cout << answer << endl;

	return 0;
}

평가

그리디 알고리즘을 생각하는 것 자체는 굉장히 쉬운 문제.
다만 많은 분들이 시간초과에서 많이 애먹을 수 있다고 생각합니다.
lower_bound를 통해 O(log N)을 통해 계산을 할 수 있었는데,
priority queue를 이용한 방법도 있다고 하니 찾아보는 것이 좋습니다.

필자는 다른 이유로 틀렸는데, 그 이유는 set은 중복 값을 저장할 수 없기 때문에
계속 틀렸다고 나왔습니다.(bag의 무게가 같은 경우)
따라서 multiset 을 통해 중복을 허용해주게 하여 해결하였습니다.