2212. 센서 (Python)

2212번: 센서

 

풀이

 먼저 입력 받은 센서의 좌표들을 오름차순으로 정렬한다. 그리고나서 각 센서들간의 거리를 구해서 새로운 리스트에 담는다. 예를 들어 예제의 입력에서 1, 6, 9, 3, 6, 7을 1, 3, 6, 6, 7, 9로 정렬한다. 그 후 각각의 거리를 구하면 다음과 같다. 

 

 이렇게 구한 거리를 내림차순으로 정렬하면 3, 2, 2, 1, 0이 된다. 이제 앞에서부터 집중국의 개수(K) - 1만큼을 버리면 된다. 가장 멀리 떨어져 있는 센서끼리는 하나의 집중국에 묶지 않음으로써 집중국의 수신 가능 영역의 길이를 줄일 수 있다. 

 여기에서 K-1만큼을 버리는 것은 다음과 같은 경우를 생각하면 쉽다. 하나의 빵을 3개로 나누기 위해서는 총 2번 칼로 자르면 된다. 센서들을 K개의 구역으로 나누기 위해서 K-1번을 자르는 것이라고 생각하면 된다.

 

코드

import sys


if __name__ == '__main__':
    N = int(input()) # 센서의 개수
    K = int(input()) # 집중국의 개수 
    sensors = list(map(int, input().split()))
    sensors.sort() # 센서를 오름차순으로 정렬

    # 만약 집중국의 개수가 센서의 개수 이상이라면 
    # 각 센서마다 집중국을 설치하면 되기 때문에 답은 0이 된다.
    if K >= N:
        print(0)
        sys.exit()

    distances = [] # 센서들간의 거리를 담아주기 위한 리스트 
    for i in range(1, N):
        distances.append(sensors[i] - sensors[i-1])
    distances.sort(reverse=True) # 내림차순으로 정렬한다.

    # K-1번 가장 큰 값들을 제거한다.
    for i in range(K-1):
        distances.pop(0)

    # 남은 거리들을 합하면 집중국의 수신 가능 영역의 길이의 합의 최솟값이 된다.
    print(sum(distances))