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;
}