백준 1202번 보석 도둑

문제링크: https://www.acmicpc.net/problem/1202

사용한 알고리즘: priority_queue..?


 보석들의 무게, 가치 가 주어지고, 담을 수 있는 무게가 각각 다른 (같을 수 있다.) 가방들이 주어졌을 때 훔칠 수 있는 보석들의 가치의 합의 최대를 구하는 문제였습니다.

문제 풀이는 다음과 같습니다.
(1) 보석의 <무게, 가치> 를 pair로 저장합니다. 이후 가치가 큰게 위로 오게끔 pq를 만들어 줍니다. 가방은 multiset을 이용하여 저장해줍니다. set이 아닌 multiset을 쓰는 이유는 담을 수 있는 무게가 같은 가방이 있을 수 있기 때문에 해당 가방의 개수를 세어주기 위함입니다.

(2) pq에서 차례로 보석을 꺼내면서 해당 보석을 담을 수 있는 가방을 lower_bound 함수를 사용하여 multiset에서 뽑습니다. 이때 해당 가방을 사용하였다는 것을 int 배열을 통해 사용할 때마다 세어주었습니다. 해당가방의 multiset의 값 ( 입력받은 가방의 수) 이 int 배열에 저장된 값 ( 사용 횟수 ) 보다 클 경우(초과) 인 경우에만 해당 가방을 사용할 수 있습니다.

(3) 보석을 해당 가방을 사용할 수 없다면 그보다 큰 (lower_bound를 사용하였으므로 해당 iterator보다 큰 가방들은 모두 해당 가방보다 많은 무게를 담을 수 잇다.) 가방들을 차례로 보며, 넣을 수 있는 가방에 보석을 넣습니다. 보석은 가치가 큰 순으로 pq에서 뽑기 때문에 들어갈 수 있는 가방에 무조건 넣어주면 됩니다.

(4) 가방을 모두 사용해 주거나 보석을 pq에서 모두 꺼낸 경우 위 과정을 끝내줍니다.


문제에서 주의할 점은 같은 가방이 여러개 들어올 수 있는 점을 의식하는 것이었습니다.
(이를 위해 set이 아닌 multiset을 사용하였습니다.)