Problem Solving/Greedy

[그리디] 백준 2212번: 센서 / 골드 5

by ggyongi 2021. 6. 11.

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

2212번: 센서

첫째 줄에 센서의 개수 N(1<=N<=10,000), 둘째 줄에 집중국의 개수 K(1<=K<=1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 이상 있으며

www.acmicpc.net

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

table = {}
for i in range(n):
    key = lst[i]
    table[key] = True

sensor = sorted(list(table.keys()))
dist = []
for i in range(len(sensor)-1):
    dist.append(sensor[i+1]-sensor[i])

dist.sort()

if k == 1:
    print(sum(dist))
elif k >= n-1:
    print(0)
else:
    print(sum(dist[:1-k]))

문제 설명이 이해하기 어려웠다.

집중국의 전파가능거리가 선으로 표시된다는 게 핵심이다.