[백준] 2212번: 센서 (Python)

문제 링크

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

2212번: 센서

 

풀이

알고리즘

[그리디]

• 여러 센서의 후보들을 묶는 것으로 생각하면 k개의 묶음을 만들면 된다.
• 센서를 오름차순하여 좌표 순으로 놓는다. ex. [1, 6, 9, 3, 6, 7] -> [1, 3, 6, 6, 7, 9]
• 원소간의 차를 표현한 리스트를 만든다. -> diff = [2, 3, 0, 1, 2]
• 2개의 묶음을 만들기 위해선 1개의 간격을 버리면 된다. -> 따라서 k개의 묶음을 만들기 위해선 간격의 값이 가장 큰 것부터 시작해서 k-1개 버린다.
• 가장 큰 간격을 버리면, 나머지 간격들의 합은 묶음 안에서의 간격들을 다 더한 값이 된다.
• 따라서 diff 정렬 = [0, 1, 2, 2, 3] 인 경우,
  • K = 2 이면 k-1개의 간격을 빼므로 뒤에서부터 k-1개를 빼고 더하면 된다. ex. [0, 1, 2, 2, 3] 중에서 [0, 1, 2, 2] 만 더하기 

풀이 코드

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

sensors = list(map(int, input().split()))
sensors.sort()
diff = []
for i in range(1, n):
    diff.append(sensors[i] - sensors[i-1])

diff.sort()

print(sum(diff[:(n-1)-(k-1)]))