03.08. 센서[Greedy Algorithm][백준 2212]

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

2212번: 센서

 

Algorithm classification : Greedy Algorithm, Sorting

 

03.08.1. Problem

Korea Expressway Corporation installed N sensors on the highway to make it ubiquitous. The problem is to set up a few central stations to collect and analyze the data collected by these sensors, but for budget reasons, it is said that up to K central stations can be built on the highway.

 

Each central station can adjust the coverage area of ​​the sensor. The reception area of ​​the central station appears as a connected section on the highway. N sensors must be able to communicate with at least one centralized station, and the sum of the lengths of the receivable areas of each centralized station must be minimized due to the maintenance cost problem of the centralized station.

 

For convenience, assume that the highway is a straight line on the plane, and the sensors are located at an integer distance from the origin, a point on this straight line. Accordingly, the coordinates of each sensor are expressed as one integer. In this situation, write a program to find the minimum value of the sum of the distances of the receivable areas of each central station. However, the length of the receivable area of ​​the central station is 0 or more, and the coordinates of all sensors do not need to be different.

 

03.08.2. Input limit

The number of sensors N (1 ≤ N ≤ 10,000) is given in the first line, and the number of central stations K (1 ≤ K ≤ 1000) is given in the second line. In the third line, N coordinates of N sensors are given as an integer. There is a blank space between each coordinate, and the absolute value of the coordinates is 1,000,000 or less.

 

03.08.3. Output

In the first line, the minimum value of the sum of the lengths of the receivable areas of the maximum K centralized stations described in the problem is output.

 

03.08.4. Solution

일직선 상에 N개의 점이 있을 때 이를 모두 포함하는 선분의 길이의 합이 최소가 되게끔하면 됩니다. 점들을 우선 정렬하고 나서 인접한 점들끼리 거리를 계산합니다. 그 후 이 거리를 어떻게 처리할 것인지 고민해보시죠.

	int data[n], dis[n-1];
	for(i = 0; i < n; i++){
		scanf("%d", &data[i]);
	}
	sort(data, data+n);
	
	for(i = 0; i < n-1; i++){
		dis[i] = data[i+1] - data[i];
	}
	sort(dis, dis+n-1);
	
	int c = 0;
	for(i = 0; i < n - k; i++){
		c += dis[i];
	}

 

여러분들에게 도움을 드리고자 Test case를 아래에 적어둡니다.

6
2
1 6 9 3 6 7
>> 5
[1,3][6,9]