https://www.acmicpc.net/problem/2212
문제에서 '수신 가능영역' 이라는 개념을 잘못 이해하여 약간 헤맸다.
1번 예제를 통해 문제를 이해해보자.
직선 도로에 센서들이 존재하고 도로에 집중국을 2개 놓아 영역의 합을 최소로 하는 문제이다.
예를 들어 집중국의 위치를 4, 9로 정한다면
위 그림처럼 1, 3, 6, 6은 4번 위치의 집중국에 가깝고 7, 9는 9번 위치의 집중국에 가까워 그림처럼 영역이 나누어지게 되고, 합은 8이 된다.
만약 집중국의 위치를 2, 7로 정한다면
위처럼 나누어지게 되며, 영역의 합은 5가 된다.
대충 감을 잡을 수 있을 것으로 보이지만 집중국 위치는 부수적이고, 영역을 나누는게 중요함을 알 수 있다.
4, 7번 위치에 집중국을 놓는 케이스는 6과 7 사이의 길이 1인 영역을 끊어 전체 영역 길이를 1만큼 줄이는 것이고 2,7번 위치에 집중국을 놓는 케이스는 3과 6 사이의 길이 3인 영역을 끊어 길이를 3만큼 줄이는 것이 된다.
요약하자면 K개의 집중국은 전체 영역을 K개로 나누며, 전체 영역에서 K-1개의 연결을 끊는 것으로 생각할 수 있다.
따라서 나눈 모든 영역들의 길이의 합 중에 최솟값을 찾고 싶다면?
센서 사이의 거리가 긴 순서대로 끊어 내어 영역을 분리한 후 남은 모든 영역들의 합을 구하면 된다.
fun main(args: Array<String>): Unit = with(System.`in`.bufferedReader()) {
val N = readLine().toInt()
val K = readLine().toInt()
val sensors = readLine().split(' ').map{it.toInt()}.sorted()
val gaps = IntArray(N-1){sensors[it+1] - sensors[it]}.also { it.sortDescending() }
var sum = 0
for(i in K-1 until gaps.size)
sum += gaps[i]
print(sum)
}코드가 정말 간단하다.
먼저 센서들 정보를 받아 정렬한 뒤, 각 센서들 사이의 거리들을 내림차순으로 정렬한 gaps 배열을 구한다.
그러면 gaps의 앞쪽에는 센서들 거리 차이 중 가장 큰 값이 오게 되며 K개의 센서는 K-1개의 연결을 끊어낼 수 있으므로, gaps 배열의 앞쪽 K-1개의 값들을 무시한 뒤 나머지 영역들의 합을 구해 출력한다.
가장 긴 센서 간 거리들부터 지운다는 것이 그리디의 성질을 띄는 문제라고 할 수 있겠다.
