[백준][Kotlin] - 순회 강연(2109)

문제 소개

🥇️ 문제 레벨 : 골드3
🔔 문제 유형 : 그리디, 우선순위 큐, 정렬
💬 풀이 언어 : Kotlin
🖇️ 문제 링크 : 백준 문제 링크

📝 문제

 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. 각 대학에서 제시하는 d와 p값은 서로 다를 수도 있다. 이 학자는 이를 바탕으로, 가장 많은 돈을 벌 수 있도록 순회강연을 하려 한다. 강연의 특성상, 이 학자는 하루에 최대 한 곳에서만 강연을 할 수 있다.

 

예를 들어 네 대학에서 제시한 p값이 각각 50, 10, 20, 30이고, d값이 차례로 2, 1, 2, 1 이라고 하자. 이럴 때에는 첫째 날에 4번 대학에서 강연을 하고, 둘째 날에 1번 대학에서 강연을 하면 80만큼의 돈을 벌 수 있다.

🤔 문제 분석

이 문제를 처음 읽을 때, "d일에 와서 강연을 하면, p를 준다."라고 이해를 했다. 너무 쉽다고 생각해서, 빠르게 코드를 작성해서 제출했는데, "틀렸습니다"가 나왔다. 10분 가량 생각을 해봤는데, 도저히 왜 틀렸는지 이해할 수 없었다.

 

결국, 질문 게시판을 찾아보게 되었고, 좋아요가 가장 많은 반례를 봤다.

5
3 3
2 3
1 3
100 4
90 4

맞는 답 : 195

내가 이해한 바에 따르면 (3 3), (100 4)만 가능하기에, 정답은 103이 나와야했지만, 정답이 195라길래 정말 이해할 수 없었다. 분명, 하루에 최대 한 곳에서만 강연을 할 수 있다고 했다. 내가 놓친게 있나 싶어서 문제를 다시 집중해서 읽어봤다.

각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불

충격적이게도 "안"이라는 키워드를 내가 빼먹고 본 것이다. d일에가 아닌, d일 안에 였던 것이다. 그래서 모든 코드를 지우고, 다시 풀이를 해봤다.

최선의 선택하기

이 문제의 핵심은 더 이득인 강연이 나오면 기존 선택을 취소해야 한다는 것이다. 즉, 어떤 강연을 선택했었는지 기억을 해야하는 것이다.

처음에는 막연히 Map을 사용해보려고 했다. 하지만, 더 이득인 강연으로 인해 가장 저렴한 강연을 취소하려면, 최소값을 찾아 삭제를 해야했다. 그러기 위해서는, 매번 전체 탐색(Full-Scan)이 필요했고, O(N)의 시간 복잡도를 가지기에 효율적이지는 않은 것 같다고 판단을 했다.

 

그래서 PriorityQueue를 사용하기로 했다. 최솟값을 찾는 데 O(1), 삭제와 삽입에 O(log N)이 걸리기 때문에, 가장 효율적인 방안이라고 생각했다.

핵심 로직

우선, 강연 정보를 모두 리스트에 담은 뒤 day를 기준으로 정렬을 한다. day로 정렬하는 이유는 단순히 1일차부터 순서대로 스케줄을 짜는 것이 편하기 때문이다.

val lectures = mutableListOf<Lecture>()  

repeat(n) {  
    val st = StringTokenizer(readLine())  
    lectures.add(Lecture(st.nextToken().toInt(), st.nextToken().toInt()))  
}  

lectures.sortBy { it.day }

이제, 이 리스트에 담긴 각각의 요소를 확인하면서 PriorityQueue에 담아주면 된다. 이 pq에 넣는 값들은 내가 선택한 강연이 된다.

val pq = PriorityQueue<Int>()  

for (lecture in lectures) {  
    pq.add(lecture.pay)  
}

하지만, 단순히 추가만 해서는 정답에 도출을 할 수 없다. 이 문제의 핵심은 더 이득인 강연이 나오면 기존 선택을 취소해야 한다는 것이다. 아까 봤던 반례를 통해 확인해보자.

lectures = [(3, 3), (2, 3), (1, 3), (100, 4), (90, 4)]

1일차 : pq(3)
2일차 : pq(3, 2)
3일차 : pq(3, 2, 1)
4일차 : pq(3, 2, 1, 100)
5일차 : pq(3, 2, 1, 100, 90)

이 반례에서 d의 최대값은 4이다. 때문에, 순서대로 계속 넣을 경우, 90을 벌 수 있는 강연을 할 수 없게 된다. 때문에, 90을 넣을 차례가 되었을 때, 가장 저렴한 강연을 지우기 위해서는 최소값을 찾아서 제거해야 한다.

 

그 방법은 단순하다. 우선순위 큐에 comparator를 따로 지정하지 않으면, 최소 힙(Min Heap)을 유지하기 때문에, pq.poll()을 하게 되면 최소값을 지우게 되는 것이다. 하지만 무턱대고 지울 수는 없다.

최소 힙이란, 루트 노드가 항상 작은 값을 가지는 것을 의미함

앞서 말한 것과 같이, pq는 내가 선택한 강연 목록이다. 즉, 스케줄표라고 생각하면 편하다. 따라서 pq.size는 현재까지의 진행 날짜(소요 일수)를 의미하게 된다. 그렇다는 것은, pq.size > lecture.day를 만족하게 될 경우, pq.poll()를 해버리면 되는 것이다.

for (lecture in lectures) {  
    pq.add(lecture.pay)  

    if (pq.size > lecture.day) {  
        pq.poll()  
    }  
}

이로써 가장 적은 페이를 주는 강연이 지워지고, 더 비싼 강연을 선택할 수 있게 된다.

😎 최종 코드

메모리 : 23680 KB
시간 : 244 ms

import java.util.*  

private data class Lecture(  
    val pay: Int,  
    val day: Int  
)  

fun main() = with(System.`in`.bufferedReader()) {  
    val line = readLine() ?: return  
    val n = line.toInt()  
    val lectures = mutableListOf<Lecture>()  

    repeat(n) {  
        val st = StringTokenizer(readLine())  
        lectures.add(Lecture(st.nextToken().toInt(), st.nextToken().toInt()))  
    }  

    lectures.sortBy { it.day }  

    val pq = PriorityQueue<Int>()  

    for (lecture in lectures) {  
        pq.add(lecture.pay)  

        if (pq.size > lecture.day) {  
            pq.poll()  
        }  
    }  

    println(pq.sum())  
}