[Swift 백준] 2212 센서

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

 

풀이 아이디어

위 예제 입력을 예시로 설명

 

1. 오름차순으로 정렬  ( 1 3 6 6 7 9 )

2. 앞자리랑 차이나는 거리 계산(gaps) ->  ( 2 3 0 1 2) 

3. 거리 차이를 최소로 만들어야 하고, 우리는 그걸 k개의 집중국 수 (그룹) 만큼으로 나눌 수 있다.

센서를 K개의 그룹으로 나누기 위해선
센서 사이를 K - 1번 끊어야 함

왜냐면,
6개의 센서를 2그룹으로 나누려면 → 1번 끊어야 하고
6개를 3그룹으로 나누려면 → 2번 끊어야 하니까.

 

4. 고로 내림차순으로 정렬된 거리 배열에서 k-1 만큼 뗴어내고 나머지를 합쳐주면 됨 

 

풀이

let n = Int(readLine()!)!
let k = Int(readLine()!)!

var input = readLine()!.split(separator: " ").map{Int($0)!}

input.sort()

if k >= n {
    print(0)
} else {
    var gaps: [Int] = []
    //3~4번 설명 참조
    for i in 0..<input.count-1 {
        gaps.append(abs(input[i]-input[i+1]))
    }
    gaps.sort(by: >)
    print(gaps[(k-1)...].reduce(0, +))
}