백준 13164 행복 유치원 Kotlin (그리디)

문제 출처 : https://www.acmicpc.net/problem/13164

13164번: 행복 유치원

문제

행복 유치원 원장인 태양이는 어느 날 N명의 원생들을 키 순서대로 일렬로 줄 세우고, 총 K개의 조로 나누려고 한다. 각 조에는 원생이 적어도 한 명 있어야 하며, 같은 조에 속한 원생들은 서로 인접해 있어야 한다. 조별로 인원수가 같을 필요는 없다.

이렇게 나뉘어진 조들은 각자 단체 티셔츠를 맞추려고 한다. 조마다 티셔츠를 맞추는 비용은 조에서 가장 키가 큰 원생과 가장 키가 작은 원생의 키 차이만큼 든다. 최대한 비용을 아끼고 싶어 하는 태양이는 K개의 조에 대해 티셔츠 만드는 비용의 합을 최소로 하고 싶어한다. 태양이를 도와 최소의 비용을 구하자.

입력

입력의 첫 줄에는 유치원에 있는 원생의 수를 나타내는 자연수 N(1 ≤ N ≤ 300,000)과 나누려고 하는 조의 개수를 나타내는 자연수 K(1 ≤ K ≤ N)가 공백으로 구분되어 주어진다. 다음 줄에는 원생들의 키를 나타내는 N개의 자연수가 공백으로 구분되어 줄 서 있는 순서대로 주어진다. 태양이는 원생들을 키 순서대로 줄 세웠으므로, 왼쪽에 있는 원생이 오른쪽에 있는 원생보다 크지 않다. 원생의 키는 109를 넘지 않는 자연수이다.

출력

티셔츠 만드는 비용이 최소가 되도록 K개의 조로 나누었을 때, 티셔츠 만드는 비용을 출력한다.

힌트

• 1조: 1, 3
• 2조: 5, 6
• 3조: 10

알고리즘 분류

• 그리디 알고리즘
• 정렬

풀이

풀이를 떠올리면 코드는 복잡하지 않지만 풀이를 떠올리기 쉽지 않은 그리디~!

우선 1 3 5 6 10의 예에서 조를 나누지 않았을 때를 생각해 보면

10 - 1로 9만큼의 비용이 든다.

위 배열에서 각 경계선에 선을 긋는다고 생각하면 차이값들은

2 2 1 4가 된다.

이 차이값들은 해당 경계에 선을 그었을 때 줄어드는 비용이다.

이 값들을 보고 어디에 선을 그어야 할지 생각해 보자.

6과 10 사이에 선을 그어 조를 나눈다고 가정하면

6 - 1 + 10-10 = 5만큼의 비용이 든다.

이 값은 조를 나누지 않았던 처음 비용 9에 10과6의 차이인 4를 뺀 값과 같다.

즉, arr[n-1] - arr[0]의 값에서 차이값이 가장 큰(조를 나눴을 때 비용이 가장 크게 감소되는) 곳에 k-1개의 선을 긋자

k-1개의 선을 긋는 이유는 문제에서 K개의 조로 나누어야 한다 했고, k-1개의 선을 그어 만들 수 있다.

이를 코드로 풀면 각 경계선의 차이값들을 모두 저장해 놓고, 이를 내림차순 정렬, 앞에서부터(차이가 큰 값부터) k-1개 선택해서 전체 비용에 빼주기

 

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()

fun main() = with(System.out.bufferedWriter()) {
    val (n,k) = getIntList()
    val input = getIntList()
    var answer = 0
    val arr = IntArray(input.size - 1)
    for (i in arr.indices) {
        arr[i] = input[i + 1] - input[i]
        answer += arr[i]
    }
    arr.sortDescending()
    for (i in 0 until k - 1) {
        answer -= arr[i]
    }
    write("$answer")
    close()
}