백준 2212번 센서 - Python

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

문제설명

예제입력 1번을 예시로 설명하자면 하나의 직선에 6개의 센서가 배치되어있고 2개의 집중국을 수신 가능 영역의 최소값이 되게끔 위치시키는 것이다.

예제1번의 경우 (1, 3)와 (6, 6, 7, 9)에 집중국을 위치시켯을때 2와 3으로 수신 가능영역의 합이 5로 최소 값이 된다.

해결방법

각 센서의 위치를 오름차순으로 정렬한뒤 각 센서간의 거리를 구한다.
(1, 3) (3, 6) (6, 6) (6, 7) (7, 9) > (2, 3, 0, 1, 2)

이 센서간의 거리를 다시 오름차순 정렬하면 0, 1, 2, 2, 3 이 나오게 되는데 이때 n-k인 6-2 = 4개를 작은값 부터 선택해서 더하면 그것이 답이 된다. 0+1+2+2 = 5

왜 n-k개를 골라야 하는지 생각해보자

센서의 개수가 6개이고 집중국의 개수가 2개 일때
(1, 3) (6, 6, 7, 9)로 나누어 지게 되는데 이때는 3과 6사이의 거리를 구할 필요가 없다 즉 위에서 센서간의 차이를 구할때 나온 3을 덧셈에 포함하지 않는 것이다.

센서의 개수가 6개이고 집중국의 개수가 3개 일때를 생각해보자

(1,3) (6, 6, 7) (9)로 나눌 수 있다. 이 때는 3과 6, 7과 9 사이의 거리를 구할 필요가 없다.

즉 두개의 거리를 덧셈에 포함하지 않아야 한다.

그렇기 때문에 n-k개의 센서 거리를 더하면 정답이 나오게 된다.

코드

import sys

input = sys.stdin.readline

n = int(input())
k = int(input())

arr = list(map(int, input().split()))

arr.sort()
length = []

for i in range(len(arr)-1):
    length.append(arr[i+1] - arr[i])
    
length.sort()

print(sum(length[:n-k]))
print(length)