[백준(BOJ)] 13164 행복 유치원 - 스위프트(Swift)

[Gold V] 행복 유치원 - 13164

문제 링크

성능 요약

메모리: 100712 KB, 시간: 200 ms

분류

그리디 알고리즘, 정렬

문제 설명

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

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

입력

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

출력

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

 

풀이

우선  최소 비용을 만들기 위해서는 한 그룹에 묶여있는 원생들끼리의 차이가 최소가 되어야 합니다.

따라서 옆자리 간의 차이를 구해줍니다. 

그리고 최소 길이부터 그룹을 나누어주면 해결됩니다.

 

K개의 조로 나누어야 하는데, 이는 N - K를 해주면 됩니다.

 

그림으로 보면 다음과 같습니다.

 

따라서 옆 자리 간 높이를 구해주고, 값이 낮은 것 부터 계산하기 위해 오름차순으로 정렬합니다. 

그 뒤 잘라야하는 조의 개수만큼 앞에서부터 높이를 더해주면 됩니다.

 

코드로 보면 다음과 같습니다.

let nk = readLine()!.split(separator: " ").map { Int($0)! }
let (n, k) = (nk[0], nk[1])
let student = readLine()!.split(separator: " ").map { Int($0)! }
var (height, sum) = ([Int](), 0)

for i in 0..<n-1 {
    height.append(student[i + 1] - student[i])  // 키 차이 값을 기준으로 새로운 배열 생성
}

height.sort()   // 오름차순으로 정렬

for j in 0..<n - k {
    sum += height[j]    // 잘려있는 부분만 더하기
}

print(sum)