백준 2212. 센서

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

2212번: 센서

 

 

13164. 행복 유치원이랑 거의 같은 문제였다. (https://tose33.tistory.com/334)  

 

우선 센서들을 정렬한후

각 센서들간의 거리를 구한다.

그리고 각 센서들을 k개의 집중국으로 묶어야 하는데, 

각 집중국의 수신 가능영역의 거리의 합의 최솟값이 되도록 하려면 센서간의 거리가 큰 값이 경계가 되도록 하면된다.

 

예제에서 각 센서의 위치가 다음과 같다고 k=2라면 

1 3 6 6 7 8 9

 

각 센서간의 거리는 다음과 같다

2 3 0 1 1 1

 

k=2이므로 두개의 집중국으로 묶을것이다.

따라서 k-1인 1개의 경계를 찾아야하고 가장 큰 거리인 3을 경계로한다.

거리 3은 센서 3,6간의 거리다.

 

따라서 (1,3) (6,6,7,8,9)를 묶는다.

답을 구할때는 그냥 최대거리인 3을 뺴고 나머지 거리들을 더하면된다.