[백준 2212] 센서

🍎[백준 2212] 센서

문제링크

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

2212번: 센서

 

⚾ 코드

import sys
input = sys.stdin.readline

n = int(input())
k = int(input())
sensors = list(map(int, input().split()))
sensors.sort()
diff = [sensors[i]-sensors[i-1] for i in range(1, n)]
diff.sort()
print(sum(diff[:n-k]))

 

🔔 해결 과정 & 깨달은 점

처음에는 각 센서 간의 거리의 차를 구한 뒤에

차가 가장 큰 곳 사이에 집중국을 세우면 되지 않을까 라고 생각했다.

그러나 이 생각은 틀렸다. 왜냐하면 가운데에 세워봤자 어차피 같은 거리를 더하기 때문이다.

예를 들어 거리가 2인 센서가 가장 차이가 크다고 할 때 그 사이에 집중국을 설치해도 어차피 2를 더한다.

 

내가 원하는 것은 가장 차이가 큰 거리를 더하지 않는 것이었다.

 

잘 생각해보니 둘을 더하지 않기 위해서는 둘을 다른 집중국에 연결시키면 되는 것이었다.

 

센서가 n개라고 할 때 센서 사이의 거리 차의 값은 n-1개가 나온다.

여기에서 k개의 센서를 설치하면 k개의 차이를 없애주는 것이 된다.

따라서 sum(diff[:n-k])를 하면 답이 나온다.