1202
-
[백준]1202: 보석 도둑 - JAVA문제풀이/백준 2021. 4. 27. 18:53
[백준]1202: 보석 도둑 www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 풀이 우선순위 큐를 사용한 문제로 굉장히 재미있게 느껴졌던 문제였다. 이 문제는 쉽게 생각하면 쉽게 풀 수는 있지만 시간복잡도에서 통과하기가 쉽지 않은 문제였다. 처음에는 우선순위큐를 사용하여 정렬을 통해 쉽게 풀 수 있을 것이라 생각했지만 역시나 시간 초과가 발생했다. 우선순위 큐를 두개를 만들어서 꺼내고 집어넣고를 반복..