[백준/BOJ] 1202번: 보석 도둑

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

1202번: 보석 도둑

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

해설

한 가방에는 한 개의 보석만을 담을 수 있다.

그렇다면 문제를 해결하기 위한 방법은 간단하다.

가방에 담을 수 있는 무게 중 가장 큰 가치를 가진 보석을 가방에 담으면 되는 것이다.

 

문제의 예제 2를 보자.

 

보석과 가방을 무게 순으로 정렬시켜준다.

처음으로 2kg 가방에는 (1kg, 65)인 보석과 (2kg, 99)인 보석이 들어갈 수 있다. 

이때 가장 큰 가격이 있는 보석은 (2kg, 99)이므로 이 보석을 2kg 가방에 넣는다.

 

이제 10kg 가방에 들어갈 수 있는 보석을 보자.

(1kg, 65)인 보석과 (5kg, 23)인 보석이 들어갈 수 있다.

이 중 더 큰 가격인 보석은 (1kg, 65)이므로 이 보석을 가방에 넣어준다.

따라서 가격의 총합이 164만큼 가져갈 수 있다.

 

이제 이를 구현하는 방법을 알아보자.

우선순위 큐를 쓰면 간단히 해결할 수 있다.

 

우선순위 큐에 보석의 무게를 오름차순으로 넣어준다.

data class Jewel(val weight: Int, val price: Int): Comparable<Jewel> {
    override fun compareTo(other: Jewel): Int = weight - other.weight
}

repeat(n) {
    val (weight, value) = readLine().split(" ").map { it.toInt() }
    pq.add(Jewel(weight, value))
}

나는 가방 무게를 배열에 저장하여 정렬했지만, 다른 자료구조를 사용해도 문제없을 것이다.

bag = IntArray(bagCnt)
repeat(bagCnt) { i -> bag[i] = readLine().toInt() }
bag.sort()

이제 가격을 저장할 우선순위 큐를 한개 더 선언할 것이다.

이 우선순위 큐에는 가방의 무게보다 보석의 무게가 작을 때, 그 보석의 가격만을 저장할 것이고, 가격이 높은 순으로 정렬되야하므로 내림차순 정렬을 한다.

전체적인 코드를 보면 다음과 같다.

소스 코드

import java.util.*

data class Jewel(val weight: Int, val price: Int): Comparable<Jewel> {
    override fun compareTo(other: Jewel): Int = weight - other.weight
}

private val pq = PriorityQueue<Jewel>()
lateinit var bag: IntArray

fun main() = with(System.`in`.bufferedReader()) {
    val (n, bagCnt) = readLine().split(" ").map { it.toInt() }

    repeat(n) {
        val (weight, value) = readLine().split(" ").map { it.toInt() }
        pq.add(Jewel(weight, value))
    }

    bag = IntArray(bagCnt)
    repeat(bagCnt) { i -> bag[i] = readLine().toInt() }
    bag.sort()

    println(stealJewel())
}

private fun stealJewel(): Long {
    var totalWeight = 0L
    val saveValue = PriorityQueue<Int>(reverseOrder())

    for(i in bag.indices) {
        val bagWeight = bag[i]

        while(!pq.isEmpty()) {
            if(pq.peek().weight <= bagWeight) saveValue.add(pq.poll().price)
            else break
        }

        if(saveValue.isEmpty()) continue
        totalWeight += saveValue.poll()
    }

    return totalWeight
}