[백준 1449번] [Kotlin] 수리공 항승

 

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

1449번: 수리공 항승

 

난이도 : 실버 3
태그 : 그리디, 정렬

 

 

설명

1, 2, 3, 4 위치에서 물이 흐르고, 길이가 3인 테이프가 있다고 할 때,

위치 1을 테이프를 막기 위해 0.5 ~ 2.5 까지 덮을 수 있습니다.

하지만 위치가 3인 곳은 고치지 못하기에,

위치 3을 막기 위해 2.5 ~ 4.5 까지 덮을 수 있습니다.

 

즉, 물이 새는 곳의 위치를 오름차순 정렬한 뒤,

가장 처음 물이 떨어지는 곳의 위치를 테이프로 막고,

방금 전에 붙인 테이프로 막을 수 없는 곳이 나온다면 또 다시 테이프를 막는 작업을 반복하면 됩니다.

 

 

 

소스코드

import java.util.PriorityQueue

fun main() = with(System.`in`.bufferedReader()) {
    val (n, l) = readLine().split(" ").map(String::toInt)

    val pq = PriorityQueue<Double>()
    pq.addAll(readLine().split(" ").map { it.toDouble() })

    var ans = 0
    var len = 0.0

    while (pq.isNotEmpty()) {
        val e = pq.poll()

        if (e  > len) {
            len = e + l - 0.5
            ans++
        }
    }

    println(ans)
}

 

len은 이전에 붙인 테이프의 끝 위치를 저장합니다.

직전에 테이프의 끝 위치보다 큰 위치가 나오면,

(현재 물이 새는 곳 위치 + 테이프 길이 - 0.5)로 갱신시키며,

테이프를 뜯은 횟수 (ans)를 +1 해줍니다.