Python - [백준]2212-센서

출처

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

문제

센서들을 거리순으로 집중국의 개수인 K개의 그룹으로 분리하는 문제이다.

접근 방법

입력으로 들어온 센서의 좌표를 오름차순으로 정렬한다.
1 3 6 6 7 9 의 경우라면, 1-3-6-6-7-9의 연결 고리를 가질 것 이고, 우리는 이것을 두개의 그룹으로 분리해야 하기 때문에 하나의 연결고리를 제거하면 된다.
연결고리는 각 센서사이의 거리이며, [2, 3, 0, 1, 2]가 될것이고 이것을 내림차순 정렬하여 3 2 2 1 0 으로 만든후 가장 긴 연결고리인 3을 끊어내 남은 연결고리의 합을 구하면 되는 문제이다.

풀이

연결고리를 거리순으로 k-1번 제거하면 된다.
예외적으로 K가 N보다 많이 주어지게 된다면 센서 각각의 좌표에 집중국을 배치하면 되기때문에 무조건 0을 출력하면 된다.

import sys
input = sys.stdin.readline
n = int(input())
k = int(input())
sensor = list(map(int, input().split()))

sensor.sort()
dist = []

if k >= n:
    print(0)
    sys.exit()
for i in range(n-1):
    dist.append(sensor[i+1] - sensor[i])
dist.sort(reverse=True)
for _ in range(k-1):
    dist.pop(0)
print(sum(dist))