[그리디/백준] 2212번: 센서

-문제: https://www.acmicpc.net/problem/2212

 

집중국과 센서 사이의 거리 차 합이 최소가 되려면 거리차가 제일 많이 나는 두 지역마다 집중국을 설치하면 된다. (이건 ok)

그러면 양끝 값의 차이를 구하고, 그 차가 가장 큰 것부터 집중국을 설치해 나가면 된다.

 

이걸 어떻게 구현해야할지 몰랐는데, 차이를 내림차순으로 정렬한 다음 큰 것부터 빼내고 남은 것들의 총합을 구하면 된다. 

첫번째 풀었을 때는 이해도 안 갔는데, 두번째는 조금 이해가 가는 것 같다. 

 

마지막 반복문은 k-1인 이유는 인접한 두 지점의 거리차 이므로 k-1개 밖에 없기 때문이다. 

 

-정답풀이:

n=int(input())
k=int(input())
data=list(map(int,input().split()))
data.sort()

distance=[]
if k>=n:
    print(0)
else:
    for i in range(1,n):
        distance.append(data[i]-data[i-1])
    distance.sort(reverse=True)
    for _ in range(k-1):
        distance.pop(0)
    print(sum(distance))