백준[2212] 센서 (Python3)

관찰이 필요한 문제 생각하는 방향에 따라서 어렵게 풀 수도 있고, 쉽게 풀 수도 있다.

지문 분석

수신 가능 영역의 길이를 최소화하기 위해선, 센서 간의 거리가 큰 곳부터 집중국을 설치해야 한다.
예제 2를 기준으로 센서들의 위치를 나열하면 3 6 7 8 10 12 14 15 18 20 이 되는데
정답이 되도록 집중국을 설치하면, 집중국의 포함 범위는 다음과 같다.

 

3 / 6 7 8 / 10 12 / 14 15 / 18 20

 

이제 각 집중국을 /로 나눈 영역 내 최대 1개의 아무 센서에 설치하면 된다.
예를 들자면, 6 7 8 위치에 있는 센서들 기준으로, 집중국은 6에 설치하나 7에 설치하나 해당 영역에서의 수신 가능 영역 길이는 항상 2이다.

 

또한, 빗금 친 곳 기준 간격을 재보면 3, 2, 2, 3로 각 센서들 간의 거리 중 가장 먼 곳 상위 4개이다.
따라서, 센서들의 간격 기준 상위 K - 1개를 제외한 값들의 합이 최적의 범위가 되는 것이다.

 

문제에서 알려준 범위에서 K < N 이란 말이 없다.
따라서, K >= N라면, 모든 센서에 하나의 집중국을 설치할 수 있으니 0을 출력한다.

 

def main():
    N = int(input())
    K = int(input())
    censors = list(map(int, input().split()))
    censors.sort()
    distances = []
    for i in range(N - 1):
        distances.append(censors[i + 1] - censors[i])
    distances.sort()
    for i in range(K - 1):
        if not distances:
            break
        distances.pop()
    print(sum(distances))

if __name__ == "__main__":
    main()