백준 1826 연료 채우기

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

마을까지의 거리 L, 현재 연료의 양 P와 각각 (거리, 연료량)값을 가진 주유소들이 주어진다.

마을에 도착할 수 있도록 방문할 주유소의 최소 수를 출력하는 문제이다.

전형적인 그리디 문제라고 생각해서, 금방 알고리즘을 구상하였다.

내 생각에 핵심 아이디어는 이동 가능 최대 거리였다.

최초 이동 가능 최대 거리는 시작 연료량인 P이고, 만약 주유소에서 연료를 넣는다면 연료값만큼 최대 거리를 증가시킨다.

1. 먼저 주유소들을 거리 오름차순으로 정렬한다. (도달 여부를 확인하기 위함)
2. 도달 가능한 주유소의 연료량 중 가장 큰 것을 반환하는 Priority Queue를 생성한다.
3. while문을 통해 거리 오름차순인 주유소들을 순회한다.
   2-1) maxDistance가 현재 주유소 거리보다 크거나 같다면 (도달 가능하면) 현재 주유소의 연료량을 PQ에 넣고 idx를 증가시킨다.
   2-2) maxDistance가 현재 주유소 거리보다 작다면 (도달 불가) PQ에서 연료값을 꺼내 maxDistance에 더하고 answer을 1 증가시킴 (idx 그대로)
4. 순회 종료 후, maxDistance가 L보다 작다면 (아직 도착하지 못함), pq에서 하나씩 꺼내 maxDistance를 늘리며 비교.

4
4 4
5 2
11 5
15 10
25 10

위 예시를 따라가며 어떻게 진행하는지 알아보자.

최초 상태는 위와 같다. 최초 연료가 10이므로 처음 maxDistance는 10이다.

1. 가장 가까운 주유소에 대해서 maxDistance보다 거리가 가까워 방문할 수 있다. 따라서 PQ에 연료량인 4를 넣는다.

2. 다음 주유소 또한 maxDistance보다 거리가 가까워 방문할 수 있다. 따라서 PQ에 연료량인 2를 넣는다.

3. 다음 주유소는 maxDistance보다 거리가 멀다. 따라서 연료를 채우지 않은 상태로는 해당 주유소까지 도달할 수 없다.

따라서 도달 가능한 주유소들 중 가장 연료를 많이 채워주는 (PQ에서 뽑은) 첫 번째 주유소에서 연료를 채우고 maxDistance를 14로 만든다.

그러면 세 번째 주유소까지 도달 가능하므로, 세 번째 주유소의 연료량인 5를 PQ에 넣는다.

4. 네 번째 주유소도 3번과 유사하게 첫 주유소에서만 연료를 채운 상태로 도달할 수 없다. 따라서 PQ에서 충전량이 5인 세 번째 주유소에서 연료를 채워 maxDistance를 19로 만들고 네 번째 주유소 연료량인 5를 PQ에 넣는다.

5. 모든 주유소를 순회한 뒤, maxDistance가 마을보다 크지 않다 (19 < 25) 따라서, 방문 가능했던 주유소들을 연료량이 큰 순서대로 (PQ에서 꺼내며) 25를 넘을 때 까지 충전한다.
   위 예시에선 네 번째 주유소에서 연료를 채워 29까지 갈 수 있다.

fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
    val N = readLine().toInt()

    // 거리 오름차순 정렬
    val stations = Array(N){
        val (d, f) = readLine().split(' ').map{it.toInt()}
        Station(d, f)
    }.sortedWith{s1, s2 -> s1.distance - s2.distance}
    val (L, P) = readLine().split(' ').map{it.toInt()}

    // 도달 가능한 주유소들의 연료 충전량 중 가장 많은 것 반환
    val pq = PriorityQueue<Int>(reverseOrder())

    var idx = 0
    var maxDistance = P
    var answer = 0
    while(idx < stations.size){
        if(maxDistance >= L) // 현재 상태로 마을 도착이 가능하면
            break

        // 마을 도착 불가능한 경우
        val next = stations[idx]
        if(maxDistance >= next.distance) { // 현재 상태로 다음 주유소에 도달 가능하면
            pq.offer(next.fuel)
            idx++
        }else{  // 현재 상태로 다음 주유소 도달 불가능하면
            val most = pq.poll() ?: break // 다음 주유소까지 못가는데 충전할 주유소가 남아있지 않으면 break
            maxDistance += most // 도달 가능한 주유소들 중 연료 많은 주유소에서 충전
            answer++
        }
    }

    // 모든 주유소 순회 후, 마을 도착 못했을 경우
    // 남은 주유소들 중 연료량 많은 순으로 하나씩 방문하며 maxDistance 늘림
    while(maxDistance < L && pq.isNotEmpty()){
        maxDistance += pq.poll()
        answer++
    }

    // 모든 주유소에서 충전해도 L에 닿지 못하면 -1
    print(if(maxDistance < L) -1 else answer)
}

data class Station(
    val distance: Int,
    val fuel: Int
)