[Python] 백준 2212번 - 센서

1. 문제정보

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

2212번: 센서

 

 

2. 풀이

수신국을 이동하며 거리를 계산하려고 했던 나에게는 굉장히 어려웠어서 다른 블로그의 풀이를 참고하여 구현했다. 수신국을 어느 센서 위에 설치해야 거리가 최소로 나올 것이라는 건 감각적으로 알겠는데 '어디에' 설치해야 하는 지를 알아내야 한다. 각 센서간의 거리를 구한 후 그 거리가 큰 곳부터 수신국을 설치하면 거리가 최소가 된다.

 

 

3. 코드

import sys

n = int(input())
k = int(input())
arr = list(map(int, input().split()))

arr.sort()

# 센서간의 거리를 오름차순으로 정리한다.
dist = []
for i in range(1, n):
    dist.append(arr[i]-arr[i-1])
dist.sort()

# n개의 센서 중 k개의 수신탑을 세웠기 때문에 n-k개의 센서거리 최솟값을 구하면 된다.
result = 0
for i in range(n-k):
    result += dist[i]

print(result)