1202 Jewelry thief

์•Œ๊ณ ๋ฆฌ์ฆ˜

1. ๋ณด์„์„ ๊ฐ€์น˜์ˆœ์œผ๋กœ ๋‚ด๋ฆผ์ฐจ์ˆœ์œผ๋กœ ์ •๋ ฌ
2. ๊ฐ€๋ฐฉ์„ multiset์— ์ €์žฅํ•จ
3. ๊ฐ€์น˜๊ฐ€ ํฐ ๋ณด์„๋ถ€ํ„ฐ ์ฐจ๋ก€๋Œ€๋กœ ๊บผ๋‚ด๋ฉด์„œ ์ ์ ˆํ•œ ๊ฐ€๋ฐฉ์„ ์„ ํƒํ•˜๊ณ , ์ง‘์–ด๋„ฃ์Œ
	-์ ์ ˆํ•œ ๊ฐ€๋ฐฉ : ๋ฌด๊ฒŒ๊ฐ€ ๊ฐ™์œผ๋ฉด ๊ฐ€์žฅ ์ ์ ˆ. ๊ฐ™์ง€ ์•Š์œผ๋ฉด ๋‚จ๋Š” ๋ฌด๊ฒŒ๊ฐ€ ๊ฐ€์žฅ ์ ์€ ๊ฐ€๋ฐฉ
	-์ฐพ๋Š” ๋ฒ•
		1. ๊ฐ™์€ ๊ฒŒ ์žˆ๋Š”์ง€ ํ™•์ธ
		2. ์—†์œผ๋ฉด, ํ˜„์žฌ ๊ฒ€์‚ฌํ•˜๋Š” ๋ณด์„์˜ ๋ฌด๊ฒŒ๋ฅผ ๋„ฃ๊ณ  ๊ทธ๋Œ€๋กœ ๋นผ๋ฉด ๋„ฃ์—ˆ๋˜ ์ž๋ฆฌ์— ์žˆ๋Š” ์˜† ๊ฐ€๋ฐฉ์˜ ๋ฐ˜๋ณต์ž๊ฐ€ ๋ฐ˜ํ™˜๋˜๋Š”๋ฐ
			์ด ๋ฐ˜๋ณต์ž๊ฐ€ multiset.end()์™€ ๊ฐ™์œผ๋ฉด ๋ณด์„ ๋ฌด๊ฒŒ๊ฐ€ ๋„ˆ๋ฌด ๋ฌด๊ฑฐ์›Œ์„œ ๋„ฃ์„ ์ˆ˜ ์žˆ๋Š” ๊ฐ€๋ฐฉ์ด ์—†๋Š” ๊ฒƒ์ด๋ฏ€๋กœ ๋‹ค์Œ๋ณด์„ ๊ฒ€์‚ฌ
			์•„๋‹ˆ๋ฉด ๊ทธ ๋ฐ˜๋ณต์ž๊ฐ€ ๊ฐ€๋ฆฌํ‚ค๋Š” ๊ฐ€๋ฐฉ์— ์ง‘์–ด๋„ฃ๋Š”๋‹ค.
	-์ง‘์–ด๋„ฃ์€ ๋‹ค์Œ์—” multiset์—์„œ ๋„ฃ์€ ๊ฐ€๋ฐฉ์„ ์‚ญ์ œํ•œ๋‹ค.

ํ‘ผ ๊ณผ์ •

1. ๋ณด์„์€ ๊ฐ€์น˜์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜๊ณ , ๋ฌด๊ฒŒ๊ฐ€ ๊ฐ€์žฅ ์ ์ ˆํ•œ ๊ฐ€๋ฐฉ์— ๋„ฃ์–ด์•ผ๋œ๋‹ค๊ณ  ์ƒ๊ฐํ•จ
2. ๊ฐ€์น˜์ˆœ์œผ๋กœ ์ •๋ ฌํ•˜๋Š” ๊ฑฐ์•ผ ์‰ฌ์šด๋ฐ ์ ์ ˆํ•œ ๊ฐ€๋ฐฉ์„ ํƒํ•˜๋Š” ๊ณผ์ •์ด ์–ด๋ ค์› ์Œ
	-N*N ๋ฐฉ๋ฒ• : ์ˆœ์ฐจํƒ์ƒ‰. ๊ฐ€๋ฐฉ๋ฌด๊ฒŒ - ๋ณด์„๋ฌด๊ฒŒ ์˜ ๊ฒฐ๊ณผ๊ฐ€ 0๋˜๋Š” ์–‘์ˆ˜์ธ ๊ฒƒ์ค‘ ์ฒซ๋ฒˆ์งธ๋ฅผ ์ ์ ˆํ•œ ๊ฐ€๋ฐฉ์œผ๋กœ ์„ ํƒ. ๋๊นŒ์ง€๊ฐ€๋ฉด ์—†๋Š” ๊ฒƒ
		-> ๋‹น์—ฐํžˆ ์‹œ๊ฐ„์ดˆ๊ณผ๋‚จ
	-NlogN๋ฐฉ๋ฒ• : ์ด๋ถ„ํƒ์ƒ‰. ์ ์ ˆํ•œ ๊ฐ€๋ฐฉ๋ฌด๊ฒŒ๋ฅผ ์ด๋ถ„ํƒ์ƒ‰ํ•จ.
		-> ๊ฐ€๋ฐฉ์„ ํ•˜๋‚˜์”ฉ ์ฐพ์„ ๋•Œ๋งˆ๋‹ค, ๋นˆ ๊ฐ€๋ฐฉ์ด ์ƒ๊ธฐ๋Š”๋ฐ, ์ด ๋นˆ๊ฐ€๋ฐฉ์ด ๋งŽ์•„์งˆ์ˆ˜๋ก ํƒ์ƒ‰์˜ ์‹œ๊ฐ„์ด ๋” ๊ฑธ๋ฆฌ๊ฒŒ ๋จ.(๋นˆ๊ฐ€๋ฐฉ์„ ํ”ผํ•˜๋Š” ์‹œ๊ฐ„์ด ๊ณ„์† ์ฆ๊ฐ€ํ•จ)
		-> ๊ทธ๋ฆฌ๊ณ  ๋ณด์„๊ณผ ๊ฐ™์€ ๋ฌด๊ฒŒ๋ฅผ ์ฐพ๋Š”๊ฒŒ ์•„๋‹ˆ๋‹ค๋ณด๋‹ˆ ์ œ๋Œ€๋กœ ์ฐพ๋Š” ๊ฒƒ ๊ฐ™์ง€๋„ ์•Š์Œ
3. ์ด๋ถ„ํƒ์ƒ‰์‹์œผ๋กœ ํ•˜๋˜, ๊ฐ€๋ฐฉ์„ ์„ ํƒํ•  ๋•Œ๋งˆ๋‹ค, ๊ทธ ์ž๋ฃŒ๊ตฌ์กฐ์—์„œ ๊ฐ€๋ฐฉ์„ ์ง€์šฐ๋˜ ๊ฐ€๋ฐฉ์„ ์ง€์šฐ๋Š” ์—ฐ์‚ฐ์ด ๋ณต์žกํ•˜์ง€ ์•Š์€ ์ž๋ฃŒ๊ตฌ์กฐ๋ฅผ ์„ ํƒํ•ด์•ผ๊ฒ ๋‹ค๋Š” ์ƒ๊ฐ์ด ๋“ฆ
	-> ์ด์ง„ํƒ์ƒ‰ํŠธ๋ฆฌ๋กœ ํ•ด์•ผ๊ฒ ๋‹ค๊ณ  ์ƒ๊ฐ์ด ๋“ฆ
4. ํ•˜์ง€๋งŒ ์†”์งํžˆ ์ด์ง„ํƒ์ƒ‰ํŠธ๋ฆฌ๋ฅผ ๊ตฌํ˜„ํ•ด๋ณธ์ ์ด ํ•œ๋ฒˆ๋„ ์—†์Œ
5. ๊ณ ๋ฏผํ•˜๋˜ ์ค‘ set๊ณผ multiset์— ๋Œ€ํ•ด ์•Œ๊ฒŒ๋จ
6. set์ธ ์ค‘๋ณต์ด ์—†๋Š” ์ด์ง„ํƒ์ƒ‰ํŠธ๋ฆฌ์ฒ˜๋Ÿผ, multiset์€ ์ค‘๋ณต์ด ์ž‡๋Š” ์ด์ง„ํƒ์ƒ‰ํŠธ๋ฆฌ์ฒ˜๋Ÿผ ์‚ฌ์šฉํ•  ์ˆ˜ ์žˆ๋‹ค๋Š” ๊ฒƒ์„ ์•Œ๊ฒŒ ๋จ

๊ณผ์ œ

1. ์ด์ง„ํƒ์ƒ‰ํŠธ๋ฆฌ ๊ตฌํ˜„ ๋ฐฉ๋ฒ•์„ ๊ณต๋ถ€ํ•ด๋ณด์ž.

์ฝ”๋“œ

#include <iostream>
#include <algorithm>
#include <set>
#define MAX 3000000
 
using namespace std;
 
typedef struct Jewelry {
	int weight;
	int value;
	bool operator < (Jewelry j) {
		if (value != j.value)
			return value > j.value;
		else
			return weight < j.weight;
	}
} Jewelry;
 
Jewelry jewelry[MAX];
multiset<int> bag;
int numOfJewelry, numOfBag;
 
long long maxValue();
 
int main() {
	cin >> numOfJewelry >> numOfBag;
	for (int i = 0; i < numOfJewelry; i++)
		cin >> jewelry[i].weight >> jewelry[i].value;
	for (int i = 0; i < numOfBag; i++) {
		int temp;
		cin >> temp;
		bag.insert(temp);
	}
 
	cout << maxValue();
}
 
//๋ฌด๊ฒŒ ๋„ฃ์–ด์„œ ํ˜„์žฌ ์œ„์น˜ ์ฐพ๊ณ , ํ˜„์žฌ ์œ„์น˜์˜ ๋‹ค์Œ๋ฒˆ ๊ฐ€๋ฐฉ์— ์ง‘์–ด๋„ฃ๋Š” ์‹
long long maxValue() {
	sort(jewelry, &jewelry[numOfJewelry]);
 
	long long value = 0;
	for (int i = 0; i < numOfJewelry; i++) {
		if (bag.empty())
			break;
		multiset<int>::iterator find = bag.find(jewelry[i].weight);
		if (find == bag.end()) {
			multiset<int>::iterator index = bag.insert(jewelry[i].weight);
			multiset<int>::iterator temp = bag.erase(index);
			if (temp == bag.end())
				continue;
			else
				bag.erase(temp);
		}
		else
			bag.erase(find);
		value += jewelry[i].value;
	}
 
	return value;
}