[백준 - Python] 2212. 센서 (그리디)

https://www.acmicpc.net/problem/2212

2212번: 센서

 

코드

import sys

n = int(input())
k = int(input())
point = list(map(int, sys.stdin.readline().split()))
point.sort()

answer = 0

wid = []
for i in range(1, len(point)):
    wid.append(point[i] - point[i-1])
wid.sort()
for i in range(k - 1):
    if len(wid) != 0:
        wid.pop()
answer = sum(wid)

print(answer)

 

N개의 센서가 있고, 이 센서들을 분석할 K개의 집중국을 세운다.

집중국의 수신 가능 영역을 조절할 수 있고, 센서는 적어도 하나의 집중국과 통신해야 한다.

유지비 문제로 집중국의 수신 가능 영역의 길이의 합의 최소값을 구하는 문제였다.

 

문제를 이해한 뒤에,

입력으로 들어온 센서 좌표를 정렬하여 각 센서 사이의 거리를 파악해야겠다는 생각이 들었다.

 

센서 사이 거리가 큰 지점들을, 한 집중국이 커버할 수 있는 센서들을 나누는 분기점으로 삼으면

집중국 수신 가능영역의 길이의 합의 최솟값을 구할 수 있다고 생각했다.

 

따라서 센서들 사이의 거리를 구해서 wid 변수에 저장한 후에

오름차순 정렬하여 가장 끝값부터 k개 만큼 제거를 해주었다.

 

생각한 대로 구현했고 통과했다.