[백준] 2212번 센서 - python파이썬

문제

 

 

 

설명

 

 

처음에는 문제의 해석이 잘 되지 않아서 푸는데 애를 먹은 문제이다.

주어진 문제를 쉽게 해석하는 능력이 아직 부족한 것 같다.

 

 

 

일단 이 문제는 N개의 센서의 정보를 수집하는 최대 K개의 집중국을 세울 때 수신 가능 영역 길이의 합의 최솟값을 구하는 문제이다.

 

 

이게 대체 무슨 소리지? 싶겠지만

 

이를 쉽게 해석해보면 N개를 K개의 구간으로 나눌 때 구간 내의 간격의 합이 최소가 되도록 하는 값을 구하면 된다.

 

 

 

 

예제1번의 센서를 좌표위치에 따라 오름차순 정렬을 하였을 때의 센서간의 간격을 나타낸 그림이다.

 

이때 2개의 구간으로 나누려면 센서는 2개가 필요하고 (집중국 하나 = 해당 집중국 담당하는 하나의 구간)

2개의 구간으로 나누게 되면  센서간의 간격중 1개가 사라지게 된다. 

 

즉, 사라지는 간격의 개수 = K-1

 

 

 

 

그렇다면 어떤 간격을 없애야 할까? 바로 간격이 최대가 되는 구간부터 K-1 개를 지워주면 된다.

 

 

 

코드

 

import sys
n = int(input())
k = int(input())

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

#집중국이 센서보다 많을경우 집중국에 설치하면 거리는 0이 됨
if k>= n :
    print(0)
    sys.exit()

dist = []
for i in range(1,n):
    dist.append(sensor[i]-sensor[i-1])
#가장 큰 간격부터 제거하기 위해 내림차순 정렬
dist.sort(reverse=True)
#k-1개만큼의 간격 제거
for _ in range(k-1):
    dist.pop(0)


print(sum(dist))