백준 2212번 '센서' 파이썬(Python) /그리디

https://www.acmicpc.net/problem/2212 난이도 : 골드5 소요시간 : 35분 [문제 설명] 지문만 읽어서는 이해하기 상당히 쉽지 않은 문제이다. 현재까지 백준에서 풀었던 860문제 중, 지문이 요구사항을 잘 표현하지 못하는 문제 top 1이라고 생각한다.

따라서 문제 이해는 아래와 같이 해주는 것이 좋다. 백준 질문 게시판에 있는 설명 글을 참고했다.

출처 : https://www.acmicpc.net/board/view/46572 N개의 센서가 주어진다. K개의 집중국을 세워야 한다.

각 센서는 무조건 1개 이상의 집중국의 영향을 받아야 한다. 구해야 할 정답: 각 집중국이 감당하는 센서들의 거리의 합이 최소가 되어야 한다.

이 때의 거리가 정답이다. [문제 풀이] k=5 문제에서 주어진 2번 예시를 보자.

센서의 위치는 1차원 좌표이므로, 위와 같이 정렬한다. 각 센서간의 거리 차를 구한다.

집중국은 센서 위치 위에 세우자. (해당 센서와의 거리가 0이...