파이썬 그리디 알고리즘 백준 2212 센서

문제

한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.

각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

입력

첫째 줄에 센서의 개수 N(1<=N<=10,000), 둘째 줄에 집중국의 개수 K(1<=K<=1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 이상 있으며, 좌표의 절댓값은 1,000,000 이하이다.

출력

첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.

풀이

k개의 집중국을 세워서 고속도로의 n개의 센서에 모두 연결되도록 해야하는데 연결 길이가 가장 짧도록 만들어야 한다.

연결을 가장 짧도록 만들기 위해서는 센서간 거리가 가장 긴 부분을 끊어 내고 센서에 연결하면 된다.

가장 긴 부분을 구하고 그 부분을 끊어내기 위해서

입력받은 센서의 위치를 오름차순으로 정렬하고 인접한 센서와의 차이를 구해 heapq 리스트에 저장한다.

heapq는 가장 작은 값으로 접근할 수 있는데 우리는 거리가 가장 큰 것을 구해야 하기 때문에

push할때 (-temp, temp) 이렇게 넣어 가장 큰 값을 구할 수 있게 한다.

(비교는 앞의 -temp로 하고 값은 뒤의 temp를 사용하면 된다.)

이후 k의 개수에 따라 k가 2라면 1번 끊어내고, 3이면 2번 끊어낼 수 있기 때문에

k-1까지 heapq의 -temp가 가장 작은 값을 pop하여 제거한다.

제거한 후 나머지 거리는 연결하여 사용해야 하므로 sum에 그대로 더해서 출력한다.

 

import sys
import heapq
n = int(sys.stdin.readline().rstrip("\n"))
k = int(sys.stdin.readline().rstrip("\n"))
nums = list(map(int, sys.stdin.readline().rstrip("\n").split()))
if(n<=k):
    print(0)
else:
    nums = sorted(nums)
    distance = []
    for i in range(0,n-1):
        temp = nums[i+1]-nums[i]
        heapq.heappush(distance,(-temp,temp))
    for i in range(k-1):
        heapq.heappop(distance)
    sum=0
    while distance:
        sum+=heapq.heappop(distance)[1]
    print(sum)