[백준] 1449번: 수리공 항승 - Kotlin[코틀린]

문제

 

1449번: 수리공 항승

---

풀이

 

 그리디 문제로 새로운 테이프를 언제 붙여줘야 하는지를 계산하는 문제이다.

 

 물이 새는 곳의 위치는 입력받아 배열에 저장하고, 이를 오름차순으로 정렬한다. 정렬된 배열을 기반으로 테이프를 붙여 주는데, 이전에 붙였던 테이프가 현재 물이 새는 곳에도 붙일 수 있다면 개수를 세지 않고 넘어간다. 붙여지는 범위는 현재 위치 + 테이프의 길이 - 1로 정하면 된다.

 

 테이프를 붙이는 범위를 현재 위치 + 테이프의 길이 - 1로 정하는 이유는 테이프를 붙일 수 있는 범위에 좌우의 0.5의 범위를 포함해야하기 때문이다. 예를 들어, 현재 위치가 3이고 테이프의 길이가 5라면, 테이프를 붙이는 범위는 3 + 5 - 1 = 7까지가 된다. 이 범위는 3, 4, 5, 6, 7 다섯 개의 위치를 커버하게 된다.

 

---

코드

 

fun main() {
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()

    val (num, tape) = br.readLine().split(' ').map { it.toInt() }
    val pipe = br.readLine().split(' ').map { it.toInt() }.toIntArray()
    pipe.sort()
    
    var cnt = 0
    var res = 0

    for(i in 0 until num) {
        if(pipe[i] > res) {
            cnt++
            res = pipe[i] + tape - 1
        }
    }

    bw.write("$cnt")
    bw.flush()
    bw.close()
    br.close()
}