[Python] 그리디 - 2212. 센서 (골5)

2212번: 센서

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

www.acmicpc.net

>>문제 포인트

- 이어진 간격에서 m-1개를 없애면 m-1개의 끊어짐이 생김= m개의 묶임이 생김

ex) 5 묶음 간에는 4개의 간격이 존재

=> 먼 간격부터 기지국의 수만큼 끊어내어 기지국 수만큼 묶음을 만들기

#아이디어 : 가장 짧은 간격부터 n-1개를 택하면 됨

#=> 가장 긴 간격부터 n개를 제거함

n= int(input()) #센서 개수

m= int(input()) #집중국 개수

#센서위치

sensor = list(map(int, input().split()))

sensor.sort()

#간격

interval=[]

before = sensor[0]

for i in sensor[1:]:

interval.append(i-before)

before=i

#간격 정렬 후 큰 것부터 m-1개 없애기

# => 간격이 m-1개 끊어지면 묶음이 m개 생기므로

interval.sort(reverse=True)

interval=interval[m-1:]

print(sum(interval))

헤이, 브로