[백준] 15553번. 난로(Kotlin)

문제

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

---

풀이(15분)

import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.*

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    var st: StringTokenizer

    // 첫 줄에서 N(구간의 개수), K(묶을 개수)를 입력받음
    st = StringTokenizer(br.readLine())
    val N = st.nextToken().toInt()
    val K = st.nextToken().toInt()

    var cnt = N
    val pq = PriorityQueue<Int>() // 간격을 오름차순으로 저장할 우선순위 큐

    // 사람이 1인 경우 바로 출력
    if (N == 1) {
        println(1)
        return
    }

    // 첫 번째 위치 입력
    val start = br.readLine().toInt()
    var last = start
    var max = N // 기본 길이 (각 구간의 최소 길이 1로 가정)

    // 중간 위치들 입력받으며 간격 계산
    repeat(N - 2) {
        val next = br.readLine().toInt()
        pq.add(next - (last + 1)) // 간격 저장
        last = next
    }

    // 마지막 위치 입력
    val end = br.readLine().toInt()
    pq.add(end - (last + 1))

    // N개의 구간을 K개로 묶기 위해 (N-K)개의 간격을 합침
    while (cnt > K) {
        max += pq.poll() // 가장 짧은 간격부터 더함
        cnt--
    }

    // 결과 출력
    println(max)
}

---

문제 풀이 전략

 

 

• 모든 구간의 간격 계산
  → 입력받은 위치들 사이의 거리(간격)를 구해 우선순위 큐(PriorityQueue)에 저장한다.
• 가장 짧은 간격부터 묶기
  → N개의 구간을 K개로 만들기 위해 (N - K)개의 간격을 합쳐야 하므로,
  간격이 작은 것부터 차례로 꺼내 합친다.
• 최종 길이 계산
  → 기본적으로 각 구간의 최소 길이 1을 더하고,
  합쳐진 간격들의 길이를 더해 최종 결과를 출력한다.