[BaekJoon] 1202번 보석 도둑 (Kotlin) 문제 풀이 [Gold 2]

문제

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

1202번: 보석 도둑

 

어떻게 풀 것인가?

처음에는 보석과 가방이라는 문제만 보고 배낭(Knack) 알고리즘 문제인줄 알았으나, 문제를 풀다보니 아닌 것을 알았다.

 

나는 정렬과 우선순위 큐를 이용하여 문제를 풀었다.

 

보석의 경우 문게로 내림차순 정렬을 하고 무게가 같을 경우 오름차순으로 정렬하고 가방은 무게를 기준으로 오름차순을 정렬하였다.

 

각 가방의 무게보다 가볍거나, 같은 보석의 가격을 우선순위 큐(내림차순)에 넣고, 큐가 비어있지 않으면 하나를 빼면된다.

 

어렵지만? 간단한? 문제였다.

 

풀면서 놓쳤던점

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000) <- 문제에서 이 부분을 놓치는 바람에 Long타입을 고려하지않고 계속 Int 타입으로 결과를 받아서 문제가 계속해서 틀렸다.

 

이 문제를 통해 얻어갈 것

우선순위 큐와 정렬

 

내 코드 

import java.util.Collections
import java.util.PriorityQueue

// 백준알고리즘 1202번 보석 도둑
data class Jew(val w: Int, val p: Int) : Comparable<Jew> {
    override fun compareTo(other: Jew): Int {
        return if (this.w != other.w) this.w - other.w
        else other.p - this.p
    }
}

fun main() = with(System.`in`.bufferedReader()) {
    val (n, k) = readLine().split(" ").map { it.toInt() }
    val list = PriorityQueue<Jew>()
    val bag = Array(k) { 0 }
    repeat(n) {
        val (m, v) = readLine().split(" ").map { it.toInt() }
        list.add(Jew(m, v))
    }
    repeat(k) {
        val c = readLine().toInt()
        bag[it] = c
    }
    var result = 0L
    bag.sort()
    val pq = PriorityQueue<Int>(Collections.reverseOrder())
    bag.forEach { bagWeight ->
        while (list.isNotEmpty()) {
            if (list.peek().w <= bagWeight) {
                pq.add(list.poll().p)
            }
            else{
                break
            }
        }
        if(pq.isNotEmpty()) result += pq.poll()
    }
    println(result)
}

 

참고

X