백준 2212번: 센서

백준 2212번: 센서

- 그리디 알고리즘과 정렬을 이용하는 문제입니다.

- 예를 들어 N = 6, K = 2 일 경우,

 

좌표 3과 6에 센서를 설치하면 2 + 3 = 5로 최솟값이 됩니다. 5 = 0 + 1 + 2 + 2 입니다. 이를 일반화 해보면 다음과 같습니다.

1. 센서의 좌표를 입력 받은 뒤, 오름차순으로 정렬합니다.
2. 각 센서 간의 거리를 구합니다.
3. 센서 간의 거리를 오름차순으로 정렬합니다.
4. 0번 index부터 n-k-1번 index까지의 총합을 구합니다.