[Greedy] 2212 센서(Python)

2212 센서 

문제

한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.

각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

입력

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

출력

첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.

예제 입력 1 복사

6
2
1 6 9 3 6 7

예제 출력 1 복사

5

예제 입력 2 복사

10
5
20 3 14 6 7 8 18 10 12 15

풀이

 

주어진 조건

센서의 개수(n)

집중국의 개수(k)

집중국을 k개를 세우면, (k - 1) 개의 영역으로 구분이 된다. 이 영역들이 수신 가능 영역이 된다. (고속도로 상에서 연결된 구간으로 나타나는 구간.)

 

첫번째 예제를 그림으로 표현해보면서 어떻게 풀어야할지 생각해보자.

센서들의 위치:[ 1, 3, 6, 6, 7, 9 ]

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

센서들의 거리: [2, 3, 0, 1, 2]

 

우리는 2개의 수신 가능 영역으로 나누어야 한다.

그런데, 수신 가능 영역의 길이의 합이 최소가 되도록하려면, 수신 가능 영역을 나누는게 좋을까?

그렇다. 센서 간의 거리 중 가장 거리가 먼 3을 경계로 두 영역으로 나누어야 한다. (1,3), (6,6,7,9)

그렇다면 수신 가능 영역 길이의 합은, 2 + (0 + 1 + 2)가 될 것이다.

 

즉, (집중국 k개로 수신 가능 영역은 k개이고, k개의 영역으로 구분되기 위해서는 k-1 개의 경계가 생기므로) 센서들 간의 거리 중 가장 먼 거리(집중국 간의 경계가 되어 고려하지 않아도 되는 거리. 여기서는 3) k-1개를 제외한 합이 수신 가능 영역의 최소 길이 합이 된다.

예제 1

 

예제 2도 같은 방식으로 풀이할 수 있겠다.

이제 풀이 방법을 알았으니, 우리의 알고리즘을 일반화 시켜보면서 풀이해보자.

1️⃣ 센서들을 오름차순으로 정렬한다. (센서들은 원점으로부터 오름차순으로 배치될 것이기 때문)

[3, 6, 7, 8, 10, 12,14, 15, 18, 20]

 

2️⃣ 센서들 간의 거리를 구하고, 오름차순으로 정렬한다. (가장 긴 거리 k-1개를 제외할 것이기 때문)

[1, 1, 1, 2, 2 ,2 ,2 ,3, 3]

3️⃣ 센서들 간의 거리 중 가장 먼 거리 k-1개를 제외한 합을 구한다. 답 출력.

센서들 간의 거리 중 가장 먼 거리 4개를 제외한 합을 구한다.

1 + 1 + 1+ 2+ 2+ 2 = 7

예제 2

 

코드

N = int(input())
K = int(input())

sensors = list(map(int, input().split(' ')))
sensors.sort()

dist = []
for idx in range(0, N-1):
dist.append(sensors[idx+1] - sensors[idx])
dist.sort()

min_sum = 0
for idx in range(0, N-K):
min_sum += dist[idx]

print(min_sum)