1202. 보석 도둑

1202번: 보석 도둑

---

이 문제는 Croatian Open Competition in Informatics 2013-2014 Contest #1에서 사용된 문제이다. 대회에서 사용된 입력이 공개되어 있으니 제출하기 전에 테스트해 보자. 압축을 풀어서 lopov를 찾으면 된다.

---

훔친 보석의 가격의 합을 최대로 하게끔 보석을 가방에 담는 문제이다.

 

대충 생각해 보면, 보석 가격이 큰 것부터 훔쳐야 할 것 같다. 이 문제는 냅색도 아니거니와 한 가방에 최대 하나의 보석만 넣을 수 있어서 DP가 필요하지도 않다. 따라서 보석을 가격의 내림차순으로 정렬해 놓고 시작하자.

 

이제 보석을 훔칠 수 있는지 판단해야 한다. 훔칠 수 있는지 없는지를 판단해야 하는 이유는 각 가방에 담을 수 있는 최대 무게가 정해져 있기 때문이다.

만약 이 보석을 훔친다면, 어느 가방에 넣어야 할까?

어떤 보석의 무게가 $m$이라면, 이 보석은 $c \ge m$인 모든 가방에 담을 수 있다. 보석의 무게와 가격은 아무 상관관계가 없긴 하지만, 나는 굳이 가장 큰 가방을 쓸 필요가 없다고 판단해서 ``std::lower_bound()``를 이용하여 보석을 담을 수 있는 가방 중 $c$가 가장 작은 가방에 보석을 담았다.

---

참고로 가방의 최대 무게를 입력받을 때 ``std::set``을 사용하면 안 된다. 중복된 값이 존재할 수 있기 때문에 ``std::multiset``을 사용해야 한다. ``std::vector``나 ``std::deque``를 쓰면 시간 초과가 나온다.