BOJ 1202 - 보석 도둑(Java)
https://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 풀이 완전 탐색으로 풀 경우 보석의 개수 N(1 ~ 300,000), 가방의 개수 M(0 ~ 100,000,000)으로 O(N*M)의 시간 복잡도를 가짐, 안될 거라 생각하고 풀어봤지만 역시나 시간초과 발생 * 시간 복잡도를 줄여야하며 우선순위 큐를 이용하여 품 우선 순위 큐를 이용한 풀이 - 가방에 대해서는 for문을 이용하여 탐색 -..
2021. 12. 31.
