백준 1202 보석 도둑

https://www.acmicpc.net/problem/1202

N개의 보석이 있고, 각 보석은 무게 M과 가격 V를 가진다.

이 보석들을 K개의 가방에 담을 건데 각 가방에는 최대 무게가 있다.

각 가방에는 최대 한 개의 보석만 넣을 수 있으며 얻을 수 있는 최대 가격을 구하는 문제이다.

보석 및 가방의 개수가 최대 300,000이므로 반복문을 두 번 이상 돌리는 것은 위험하다 볼 수 있다.

풀이를 시도할 때 계획한 내용은 다음과 같다.

각 가방에 보석을 최대 한 개만 넣을 수 있으므로, 가격이 비싼 보석부터 해당 보석을 넣을 수 있는 가방의 lowerbound를 구해 넣는 것을 반복한다.

이를 위해서는 보석을 가격 내림차순으로 정렬하고 가방을 무게 오름차순으로 정렬한다.

그리고 각 보석 (비싼 순)에 대해 해당 보석의 무게에 대한 가방의 lowerbound를 구해 그 가방에 넣는다.

이를 반복한다.

정렬 두 번 + 보석 순회 + lowerbound 이진 탐색 + 가방 제거 $2 * O(nlogn) + O(n) + O(logn) + O(n)$으로 $O(nlogn)$이라 가능할 것 같았으나, 시간 초과가 났다.

아무래도 이진 탐색을 위해 이미 담은 가방은 매번 리스트에서 제거해 줘야 하므로 그 부분에서 시간이 오래 걸린 것 같다고 생각된다.

그래서 고민을 좀 더 해보다 다른 사람의 풀이를 보았다.

풀이 알고리즘은 아래와 같다.

1. 보석과 가방을 무게 오름차순으로 정렬한다.
2. 가격이 비싼 순으로 뽑아오는 Priority Queue를 준비한다.
3. 각 가방에 대해, 해당 가방과 같거나 가벼운 보석들은 PQ에 넣는다.
4. 다음 보석의 무게가 현재 가방보다 무겁다면, 해당 가방에 PQ에서 뽑아온 보석을 넣고(가격을 추가하고) 다음 가방으로 이동한다.
5. 모든 가방을 순회했으면 가격 합을 출력하고 종료한다.

정렬 두 번 + 가방 및 보석 1번 순회 + PQ에 삽입 및 꺼내기만큼의 시간이 소요된다.

import java.util.*

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val (N, K) = readLine().split(' ').map{it.toInt()}

    val pq = PriorityQueue<Jewelry>{j1, j2 -> j2.price - j1.price }

    val jewelryInfo = Array(N){
        val (w, p) = readLine().split(' ').map{it.toInt()}
        Jewelry(w, p)
    }.sortedWith{j1, j2 -> j1.w - j2.w}

    val bags = IntArray(K){readLine().toInt()}.sortedArray()

    var sum = 0L
    var idx = 0
    for(bag in bags){
        while(idx < jewelryInfo.size && bag >= jewelryInfo[idx].w){
            pq.offer(jewelryInfo[idx++])
        }
        if(pq.isNotEmpty()){
            sum += pq.poll().price
        }
    }

    print(sum)
}

data class Jewelry(
    val w: Int,
    val price: Int
)