센서

문제

풀이

그리디로 풀면 되는 문제이다.
수신 가능 영역의 길이의 합을 최소화 해야 한다.

예제 입력1
[ 1, 6, 9, 3, 6, 7 ] 을 정렬 해보자
[ 1, 3, 6, 6, 7, 9 ] 가 된다.
각 사이의 차이를 구해보자
[ 2, 3, 0, 1, 2 ]가 된다.
문제에서 k는 2이므로 가장 큰 숫자인 3을 기준으로 나누면 2가 된다.
따라서 [2], [0,1,2] => [1, 3] [6, 6, 7, 9]로 나눈 것과 같다.

예제 입력2
[20, 3, 14, 6, 7, 8, 18, 10, 12, 15]을 정렬 해보자
[3, 6, 7, 8, 10, 12, 14, 15, 18, 20]가 된다.
각 차이를 구해보자
[3, 1, 1, 2, 2, 2, 1, 3, 2]
k는 5이므로 4개를 기준으로 나누면 5개가 된다.
즉 가장 큰 숫자 기준으로 4개([3, 3, 2, 2])를 나누어보면 최소가 된다.

코드

def solution():
    n = int(sys.stdin.readline())
    k = int(sys.stdin.readline())

    censor = list(map(int, sys.stdin.readline().split()))
    censor.sort()
    gap = []
    for i in range(n-1):
        gap.append(abs(censor[i + 1] - censor[i]))
    gap.sort()
    for _ in range(k-1):
        if gap:
            gap.pop()
    print(sum(gap))
solution()