백준 2212

_Bibidi 2021. 1. 9. 09:52

2212번: 센서

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

www.acmicpc.net

1. 수신 길이는 반지름이 아니라 지름으로 생각해야 함.

2. 이후 이 지름이 어느 범위를 커버하는지 생각해야 함.

3. 각 기지국이 커버하는 구간이 생기면 그 구간들 사이의 거리는 사라짐. 그럼 어느 거리를 지워야 하는가에 대한 문제로 바뀜.

4. 긴 거리를 k - 1 개 지우는 것은 짧은 거리 n - k개를 더하는 것과 같음. 편한대로 구하면 됨.

- Source code link