문제 링크

센서

문제 설명

직선의 고속도로 위에 N개의 센서를 설치하려고 한다. 이 센서들이 수집한 자료를 분석할 최대 K개의 집중국을 세우는데, 각 센서는 반드시 1개 이상의 집중국과 통신가능해야 한다. 각 집중국의 수신 가능영역의 거리의 합의 최솟값은?

IN

• 센서의 개수 (1<=N<=10,000)
• 집중국의 개수 (1<=K<=1000)
• N개의 센서의 좌표

OUT

• 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값

문제 풀이

느낌이 왔다. 뭔 느낌이냐면 내가 제일 약한 그리디의 느낌,,^_ㅠ
기록과 정리의 공간님 풀이를 참고했다...

N개의 센서를 k개의 구간으로 나누는 것과 같다.

1. 입력받은 센서의 위치를 오름차순으로 정렬
2. 인접한 각각의 센서 사이의 거리를 dist 배열에 저장
3. dist를 내림차순으로 정렬
4. 가장 큰 값 순으로 k-1개 제거
5. 남은 값의 합이 정답

import sys

input = sys.stdin.readline
sensor = int(input())
base = int(input())
coord = list(map(int, input().split()))
coord.sort()

#기지국의 개수가 센서의 크기와 같거나 크면 -> 센서의 위치에 그냥 설치
if sensor <= base:
    print(0)
    sys.exit()

dist = []

#각 인접 센서 사이의 거리
for i in range(1, sensor):
    dist.append(coord[i]-coord[i-1])
dist.sort(reverse=True)

#k개의 구간으로 나누기 -> 가장 큰 원소부터 k-1개 제거
for i in range(base-1):
    dist.pop(0)

print(sum(dist))