[백준 1202 C++] 보석 도둑

오늘은 백준(BOJ) 1202번 해킹 문제에 대해 다뤄볼 예정이다.

해킹 문제 링크 (백준(BOJ) 1202번 문제): https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

 

문제 설명

백준 1202번 보석 도둑 문제는 보석의 무게와 가격이 주어지고, 각 가방의 무게가 주어지는데 도둑이 가방에 담을 수 있는 보석의 최대 가격을 구하는 문제이다. 예를 들어, (1, 65) (5, 23) (2, 99) 보석들이 있을 때, 무게가 10(A), 2(B)인 각 가방에 넣을 수 있는 보석의 최대 가격을 구하는 것으로, B 가방에 무게가 1이고 가격이 65인 보석, A 가방에 무게가 2이고 가격이 99인 보석을 넣으면 보석의 최대 가격을 구할 수 있게 된다. 

 

문제 풀이 

이 문제의 핵심은 가방에 들어갈 수 있는 보석 중 가장 가격이 비싼 보석을 담기 위해 우선 순위 큐(Priority Queue)를 사용하는 것이었다. 

 

알고리즘

1. 보석의 무게를 기준으로 오름차순으로 정렬(Sort)해준다. 

2. 가방의 무게를 오름차순으로 정렬(Sort)해준다. 

3. 보석의 무게가 가방의 무게 보다 작을 경우 우선순위 큐(Priority Queue)에 보석을 넣어준다. 

4. 큐가 비어있지 않다면, 가장 비싼 보석을 꺼낸다. 

5. 3-4를 반복한다. 

 

이를 코드로 구현하면 아래와 같다.