[python] 백준 2212 센서

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

2212번: 센서

문제 해결

처음에 문제 이해하는데 오랜 시간이 걸렸다.

'각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. ' 가 주요 문장이다. 이 말은 수신 가능 영역을 open set(열린 집합)으로 나타낼 것인데 그 길이의 합을 물어보는 것이다.

n=5, k=2 일 때 수신 가능영역의 거리의 합 5인 경우

그려면 너무 간단하게 이웃과 거리 n-1개 중 길이가 긴 k-1개를 집중국과 다른 집중국과의 거리로 생각하여 전체 길이에서 빼주면 된다.(위에 그림에서는 4와 7사이 거리가 3으로 가장 길기 때문에 집중국과의 거리로 생각하고 수신 가능한 거리에서 제외 시켰다. 

 

CODE

import sys
input = sys.stdin.readline

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

if k>= n:
    print(0)
    exit()
dist = []
for i in range(1,n):
    dist.append(A[i]-A[i-1])
dist.sort(reverse=True)
for _ in range(k-1):
    dist.pop(0)
print(sum(dist))