Stargazer

접근: 가방에는 무조건 1개만 넣을 수 있고, 최대한 넣었을 때 가장 가치가 높은 거를 넣어야 하는데, 가방 중에 가장 작은 가방에 들어갈 정도의 보석이라면, 다른 가방에는 무조건 들어갈 수 있게 된다. 전략: 가방과 보석을 크기 오름차순으로 정렬을 한다. 모든 가방을 조사하면서, 이 가방에 들어갈 수 있는 보석을 모두 꺼내어 놓은 뒤, 이 중 가장 가치 있는 것을 넣어서 하나 씩 가방을 채운다. 그렇게 되면, 들어갈 수 있는 가방 중에 가장 가치 있는 것 부터 넣을 수 있게 된다. 이때, 우선순위 큐를 이용하면, 가방에 들어갈 수 있는 보석 중에 가장 가치 있는 것을 선택하기 수월하다. 각 보석은 조사할 때 한 번 우선순위 큐에 들어간 보석은 더는 조사하지 않는다. 이유는 우선순위 큐의 성질에 의해서 ..