[백준 2212번] 센서 문제 풀이

< 문제 >

 

 

< 입출력 >

 

 

 

 

< 풀이 >

문제가 이해되지 않아 계속 읽었다.. 결론적으로 센서는 같은 위치에 있을 수 있고, 센서의 수신 가능 영역이 0일 경우, 센서와 집중국의 위치를 같은 위치에 놓으면 된다.

따라서, 이 문제는 센서 사이의 거리를 가장 줄일 수 있도록 하면 수신 가능 영역의 합이 최소가 되므로, 센서 사이의 거리를 정렬한 뒤 가장 긴 거리를 K개 만큼 줄이면 된다. (K 개의 연결을 끊어주는 것!)

 

 

 

 

 

< 코드 >

import sys
input = sys.stdin.readline

n = int(input())
k = int(input())

sensor = list(map(int,input().split()))     
sensor.sort()        
dist = []

for i in range(n-1):
    dist.append(sensor[i+1] - sensor[i])    # 센서 사이의 거리 차 저장

dist.sort()
print(sum(dist[0:n-k]))   # 가장 먼 k개의 거리는 끊어서, 최소값 구함