2212 - 센서 (Python)

문제

한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 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

 

센서의 개수는 6개이며, 정렬을 하면 1 3 6 6 7 9 가 됩니다.

그림으로 나타내면 아래와 같은 그림이 나올 거고 ( 초록색이 센서 )

 

예시 그림

인간의 계산으로 영역의 길이를 계산해보면,

1 ~ 3 구간에 집중국을 하나, 6 ~ 9 구간에 집중국 (= 구간의 수) 을 하나 설치하는 게 좋아 보입니다. 

 

그래서 첫번째 1~3구간의 영역의 길이 3 - 1 = 2, 두 번째 6~9 구간의 영역의 길이 9 - 6 = 3

둘이 합쳐 5가 반환되는 문제입니다.

 

풀이

문제는 구간을 어떻게 나누냐가 중점이 된다고 할 수 있겠습니다.

힌트는 위 분석의 예시 그림에 있습니다.

 

정렬된 센서간의 거리가 큰 순서로 구간을 나누는 것이 이 문제의 핵심 포인트입니다.

센서를 정렬하고 앞 뒤 센서와의 거리 차이를 구해보면 아래와 같이 나오는데

 

센서 거리 차이

 이 거리 차이가 제일 큰 순서대로 구간 (=집중국 수) 을 나누면 되겠습니다.

-> 위 분석의 예시 그림을 보시면 왜 그렇게 산정해야 하는지 알 수 있습니다.

 

• 설치할 수 있는 집중국 수가 2개라면

거리 차이가 가장 큰 3으로 2 구간을 나누면 되고

 

• 만일 3개가 된다고 하면

거리 차이가 가장 큰 수인 3 다음의 수인 2의 아무 곳에서나 나누면 되겠습니다.

-> 앞의 2나 뒤에 2나 똑같은 상황이 나옴

 

• 또한, 집중국 수가 센서의 수보다 많다면

센서의 위치마다 집중국을 세우면 되니 영역의 길이는 모두 0 즉 0이 리턴되면 되겠습니다.

 

구분이 완료된 센서 간의 거리는 우리가 구해야 하는 구간의 길이 와 동일합니다.

그러므로, 센서 간의 거리의 최댓값 ( = 구간을 구분하는 기준 )을 구간의 수 - 1 ( = 구분선의 개수) 만큼 제거해주면 원하는 값을 도출할 수 있습니다.

 

이 풀이를 코드로 구현하면

 

 

PyCharm 캡쳐

집중국의 수가 더 클 때는 0을 반환하고

아니면 정렬한 후 

센서 간의 거리를 계산해서 배열에 넣은 뒤

(집중국의 수 - 1 = 구간을 나누는 기준의 수) 만큼 최댓값을 제거해주는 코드입니다.

소스 코드

import sys

sensor_count = int(sys.stdin.readline())
concen_count = int(sys.stdin.readline())

sensors = list(map(int, sys.stdin.readline().split()))

if sensor_count < concen_count:
    print(0)
else:
    sensors.sort()
    distance_array = []

    for index, sensor in enumerate(sensors):
        if index != len(sensors) - 1:
            distance_array.append(sensors[index + 1] - sensor)

    for i in range(concen_count - 1):
        distance_array.remove(max(distance_array))

    print(sum(distance_array))