[백준] [C++] 1202번 보석 도둑 (greedy, priority queue)

1. 문제 1202번: 보석 도둑 (acmicpc.net) 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 2. 풀이 이 문제는 탐욕법으로 해결할 수 있다. 가장 값비싼 보석을 가능한 가방중 가장 용량이 작은것에 넣는 것이다. 하지만 배열을 사용하여 문제를 풀 시 시간초과가 나온다. 따라서 적절히 사용한 가방을 제외 하고, 빠르게 작은 가방을 찾을 수 있는 자료구조를 사용해야한다. map을 사용하면 빠르게 원소를 제외할 수 있고, 최소 원소 또한 찾..

2021.06.30