[BOJ 2212, Python 3] 센서

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

2212번: 센서

 

풀이

구간을 구하는 것이므로 가능한 짧은 기지국과 기지국 사이의 거리만 더해주면 되기 때문입니다.

센서 사이의 길이들을 구하고 내림차순하여 n - (k - 1)개의 길이를 더해주면 됩니다.

 

증명

문제를 다른 관점으로 살펴보면 전체 센서 사이의 거리는 전체 길이는 다음 그림과 같이 구할 수 있습니다. 이 길이는 한 기지국만을 사용했을 때의길이 입니다.

여기서 기지국을 하나 더 추가하여 기지국을 2개가 주어진다면 이렇게 빈 칸이 한 칸 뚫리게 됩니다.

 

기지국이 3개가 주어진다면 또 빈 칸을 하나 뚫을 수 있게 됩니다.

이런 방식을 이용하여 이 문제는 센서와 센서 사이의 거리가 주어졌을 때 n - (k - 1)개를 선택한 합의 최솟값을 구하는 문제로 치환할 수 있습니다.

 

 

 

 

이때 k >= n일 때는 예외 처리를 해주면 됩니다.

코드

n = int(input())
k = int(input())
arr = sorted([*map(int, input().split())])
if k >= n:
    print(0)
    exit()
diff = sorted([arr[i+1]-arr[i] for i in range(n-1)])
print(sum(diff[:n-k]))