[백준 2109번] [Kotlin] 순회강연

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

2109번: 순회강연

 

난이도 : 골드 3
태그 : 자료구조, 그리디 알고리즘, 우선순위 큐, 정렬

 

 

설명

d일 안에 강의를 하러 오면 p만큼의 돈을 받을 수 있습니다.

n개의 강의를 갈 수 있을 때, 최대로 벌 수 있는 돈을 구하는 문제입니다.

 

이 문제를 처음 봤을 때 든 생각은,

아! 일자를 오름차순 정렬하고, 돈을 내림차순 정렬하면 되겠구나! 생각했습니다.

하지만, 머지않아 몇 개의 반례가 떠올랐습니다.

번호	일자	돈
1	1	100
2	2	10
3	3	200
4	3	300

위와 같이 강의가 있을 때, 처음 생각했던 알고리즘 대로라면

1,2,4 번 강의를 하러 갑니다.

따라서 100 + 10 + 300 = 410을 벌 수 있습니다.

 

하지만, d일 안에 강의를 하러 가면 되므로,

실제로는  1일차에 1번 강의, 2일차에 3번 강의, 3일차에 4번 강의를 뛰러 가는 것이

100 + 200 + 300 = 600으로 더 많은 돈을 벌 수 있습니다.

 

따라서, 

이미 강의가 잡혀있는지 체크할 days<Boolean> 배열을 하나 만들고,

강의 자료형 Lecture(price, day)를 만들고, 이로 PrioryQueue를 하나 만듭니다.

단, pq의 우선순의는 price 기준 내림차순으로 설정하였습니다.

 

pq에서 하나씩 꺼내, 해당 날짜가 이미 강의가 예약되어 있다면,

이전 날짜중 가장 가까운 가능한 날짜를 찾아 강의를 잡습니다.

 

 

 

소스코드

import java.util.*

data class Lecture(val price: Int, var day: Int)

fun main() = with(System.`in`.bufferedReader()) {

    val pq = PriorityQueue<Lecture> { o1, o2 ->
        o2.price - o1.price
    }

    repeat(readLine().toInt()) {
        // 돈, 기간 순으로 주어짐
        val st = StringTokenizer(readLine())
        pq.offer(Lecture(st.nextToken().toInt(), st.nextToken().toInt()))
    }

    // 강의가 잡혀있는지 체크
    val days = Array(10001) { false }

    var sum = 0L
    
    while (pq.isNotEmpty()) {
        val target = pq.poll()
        // 강의가 잡혀있지 않다면
        if (!days[target.day]) {
            days[target.day] = true
            sum += target.price
        } else {
            // 강의가 잡혀있다면
            var day = target.day
            
            // 이전일 중 가장 가까운 날을 찾음
            while (day > 0) {
                if (!days[day]) {
                    days[day] = true
                    sum += target.price
                    break
                } else {
                    day--
                }
            }
        }
    }

    println(sum)
}

 

 

 

후기

우선순위 큐 조건을 일자 오름차순 + 가격 내림차순으로 하면 되겠다! ...... 안되겠는데?

그럼 일자 내림차순 + 가격 내림차순으로 하면 되겠네...? 안될거같은데...;

그럼 순수 가격 내림차순 + 별도의 날짜 체크 boolean 배열을 만들어서 할까? ..... 되네?