[백준 1781] - 컵라면(Kotlin)[골드2]

문제

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

 

문제 풀이

처음 문제를 보고 난이도에 비해 정말 쉽다고 생각했다.

회의실 배정과 유사하게 우선순위큐를 사용해서, deadLine이 짧은 순, 가치가 무거운 순으로 정렬한 뒤, 시간에 맞게 빼면 된다고 생각했다.

 

우선 문제에 대한 테스트케이스는 다음과 같다.

해당 작업들을 우리가 목표로 하는 최대의 가치의 순서로 작업할 수 있도록 정렬해줘야 한다.

고려해야할 점은 다음과 같다.

• 데드라인이 적은 순서대로 정렬을 한다.
• 가치가 많은 순으로 정렬을 한다.

위 조건을 고려해서 정렬을 하면 다음과 같다.

그리고 데드라인 별로 작업을 선택해서 답을 구하면 된다.

하지만 여기서 함정이 존재한다.

내가 풀이했던 방식은 데드라인이 아니라, 그때 풀어야 했던 문제라고 생각했던 것이다.

즉 1초에는 데드라인이 1인 문제를, 2초에는 데드라인이 2인 문제를 풀어야 한다고 생각했지만, 데드라인의 개념은 사실상  그게 아니다.

n 초까지만 완료하면 되는 문제이다.

즉 1초라고 해서 반드시 1초에 문제를 푸는 것이 아닌 1~n 초까지의 문제를 풀 수 있는 것이다.

 

대표적인 예시케이스로 다음과 같다.

다음과 같은 입력에서 내 코드는 1일 차에 14, 2일 차에 10, 3일 차에 8, 4일차에 18, 5일차에 5를 선택해, 가치의 총합은 55이다.

하지만 3일차에 5번을 선택하는 것보단 6번을 선택하고, 4일 차에 7번을 선택하는 것이 더 가치의 총합은 높다(이때 총합은 59이다).

 

즉 뒤의 문제까지 고려해서 담아야 하는 것이다.

이 로직을 생각하는데 조금 오래 걸렸었다.

n의 최댓값은 200,000이기 때문에 N^2의 알고리즘으론 문제를 풀 수 없다.

즉 한 번의 탐색으로 문제를 해결해야 했고, 매번 문제를 선택하기 전에 뒤 문제를 탐색할만한 시간적 여유가 부족하다.

문제를 선택하기전 뒤 문제를 탐색하는 로직은 적절하지 않다.

 

더 근본적으로 다가가면, 5번 문제가 선택되지 않는 이유는 무엇일까?

3초~n 초까지의 문제 중 선택할 수 있는 문제는 4번부터 9번까지의 문제일 것이다.

5번 문제의 가치는 8이고, 6번 문제의 가치는 18이다. 즉 3초일 때 6번을 담는 것이 이론적으로 맞고, 이를 프로그램적으로 구현하기가 굉장히 어렵다.

 

사실상 문제를 선택하고, 선택하지 않는 이분법적 경우의 수를 통해서 완전탐색으로 문제를 해결할 수도 있지만, n이 너무 크기 때문에 이 방법은 적절하지 않다.

 

따라서 나는 선택한 문제를 임시적으로 저장할 우선순위큐를 하나 더 두었다.

우선순위큐에는 문제들의 가치가 들어가고, 오름차순으로 정렬된다.

우리는 우선순위큐를 하나씩 꺼내서 해당 시간에 풀 수 있는 문제인지를 판단한다.

하지만 해당 시간에 풀 수 없는 문제라면 문제를 선택하지 않는 것이 아닌, 앞에서 풀었던 문제들의 가치와 비교해서, 더 유망한 문제라면

앞에 풀었던 문제가 아닌 현재 탐색하고 있는 문제를 푸는 것이 유망한 선택이다.

 

코드로 보면 편할 것이다.

var time = 1
val task = PriorityQueue<Int>()
while (!pq.isEmpty()) {
    val now = pq.poll()
    if (time <= now.deadLine) {
        task.add(now.weight)
        time += 1
    } else {
        if(task.peek()<now.weight){
            task.poll()
            task.add(now.weight)
        }
    }
}

task는 선택한 문제들이 들어간다.

time을 기준으로 deadLine이 더 길다면 당연하게 문제를 풀 수 있다.

그리고 문제를 풀었다면 문제를 푸는 데 걸리는 시간은 1 초기 때문에 시간을 증가시켜 준다.

그리고 만약 현재 시간보다 데드라인이 더 짧은 문제가 있을 것이다.

이 문제는 앞에서 풀었을 때 더 유망한 선택지가 될 가능성이 있다.

따라서 풀었던 문제들의 집합인 task에서 가장 적은 가치인 문제와 비교해서, 만약 가치가 크다면 문제를 바꿔준다.

 

두 개의 우선순위큐를 통해서 문제를 선택할 때 뒤 문제까지 탐색하지 않아도 되는 효과를 볼 수 있었던 좋은 문제였다.

연료 채우기와 정말 비슷한 문제라고 생각하는데 이 문제도 좋으니 풀어보면 좋을 것 같다.

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

 

 

전체 코드

import java.util.*

class Solution {

    private val br = System.`in`.bufferedReader()
    private var n = 0

    data class Task(val deadLine: Int, val weight: Int)

    private val pq = PriorityQueue<Task>(compareBy({ it.deadLine }, { -it.weight }))

    fun run() {
        input()
        print(solution())
    }

    private fun input() {
        n = br.readLine().toInt()
        repeat(n) {
            val (d, w) = br.readLine().split(" ").map { it.toInt() }
            pq.add(Task(d, w))
        }
    }

    private fun solution() : Int{
        var time = 1
        val task = PriorityQueue<Int>()
        while (!pq.isEmpty()) {
            val now = pq.poll()
            if (time <= now.deadLine) {
                task.add(now.weight)
                time += 1
            } else {
                if(task.peek()<now.weight){
                    task.poll()
                    task.add(now.weight)
                }
            }
        }
        var answer = 0
        while(task.isNotEmpty()){
            answer+=task.poll()
        }
        return answer
    }
}

fun main() {
    Solution().run()
}