[백준2212/골드5] 센서 - Python

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

 

센서 설치 구간을 중점으로 반지름이 일정하게 센서가 수신된다는 뜻인줄알고 예제를 이해하기 어려웠다.

그래서 센서 설치 구간부터 양옆으로 거리가 일정하지 않아도 된다면 예제가 맞길래 그렇게 이해하고 풀었다.

 

[예제 1]

6
2
1 6 9 3 6 7

 

여기서 센서의 좌표를 정렬하면

1 3 6 6 7 9

이렇게 되고 이때 최솟값은 (1 3) (6 6 7 9) 이렇게 묶으면 거리의 합이 5로 최솟값이 된다.

이때 K개의 묶음의 수를 만들 수 있는 방법은 센서 배열에서 K-1번 자르면(예제에서는 정렬 후 3과 6 사이)

K개의 묶음이 나온다고 생각했다.

 

어디를 자를지 생각하다가 조합으로 모든 경우의 수를 구할까 했는데, 시간 초과가 날 것 같았다.
그래서 다시 생각해보니, 정렬된 센서들의 사이 값 중에서 가장 차이가 큰 것을 N-K개만큼 자르면 된다.

 

# 성공 코드

N = int(input()) # 센서 수
K = int(input()) # 집중국 수
sensors = list(map(int, input().split()))
sensors.sort()

dist = [sensors[i] - sensors[i-1] for i in range(1, N)] # 각 좌표 사이의 거리
dist.sort() # 작은 것부터 정렬
print(sum(dist[:N-K])) # 가장 작은 것 N-K개의 합이 최솟값