[BOJ] 1202 :: 보석 도둑

https://www.acmicpc.net/problem/1202

으엉 ㅠㅠ

어려웠고 엄청 많이 틀렸던 문제라서 문제풀면서 느낀거 정리하려고 씀

1. 그리디한 문제. 가장 큰 가격 부터 가방에 담으려고 시도 -> 가방에 담을 때 자신보다 크거나 같은 가방 중 가장 작은 가방을 찾아야함

2. 정말 naive하게 풀면 nk가 나오는데 물론! 시간초과

3. 지금 담으려는 무게보다 크거나 같은 것 중 가장 작은 가방을 찾는 과정에서 시간을 줄이기 위해 lower_bound를 생각함(logN)

4. lower_bound로 담을 수 있는 가방을 찾고 그 가방을 사용했다는 표시?를 하기위해 erase연산을 사용헀으나, vector에서 erase연산은 n의 시간복잡도를 가지므로 약 n^2logn이 나와 시간초과

5. 우선, pq를 사용해보라는 조언을 듣고, 가격이 큰 것 부터 찾는 과정을 보석의 가격을 pq에 담아 정렬과정과 pop과정에서의 시간을 줄임

6. 그 후 erase연산에 들어가는 시간을 줄여야 하는데,,, 이과정에서 엄청 애먹었던게, 일단은 vector를 그대로 써보자!하는 욕심에 lower_bound로 iter을 찾아 그 부분의 값을 -1로 바꾸었는데 계속 틀렸다고 뜸

7. 혼자 예제 몇개 만들어서 풀어본 결과 -1로 만들면 while문(가격이 큰 순서 대로 보석을 비교하는 과정)에서 매번 sort를 해야하는데 이걸 빼먹었었음! 그래서 while문 안에서 sort를 했는데 역시 시간초과

8. 정렬된 구조를 유지할 필요? 가 있다고 느낌. pq에서 lower_bound를 쓸수있나? 음...그걸 모르곘어서 일단 multiset써서 해결ㅠ

9. 사실 multiset에서 erase할 떄 시간복잡도 아직 잘 모름...자구공부를 다시해야하나 흑흑

+) 지금 추가로 알게 된 것. set은 이진탐색트리 구조를 하고있고 그래서 검색할 때 log 시간복잡도를 보장한다. 그래 그럼...그러면 erase의 시간복잡도는 몰까 흑흑 생각해바야지

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
using namespace std;
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(NULL);
	priority_queue<pair<int, int> > info;
	multiset<int> m;
	int n, k;
	cin >> n >> k;
	for (int i = 0; i < n; i++)
	{
		int weight;
		int price;
		cin >> weight >> price;
		info.push(make_pair(price, weight));
	}
	for (int i = 0; i < k; i++)
	{
		int temp;
		cin >> temp;
		m.insert(temp);
	}
	long long ans = 0;
	while (!info.empty())
	{
		int weight_need = info.top().second;
		int price_now = info.top().first;
		info.pop();
		auto locate = m.lower_bound(weight_need);
		if (locate != m.end())
		{
			m.erase(locate);
			ans += price_now;
		}
	}
	cout << ans << '\n';
}