🚨Problem
https://www.acmicpc.net/problem/2212
한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.
각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.
편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.
입력
첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있으며, 좌표의 절댓값은 1,000,000 이하이다.
출력
첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.
Solution
센서의 개수 N, 집중국의 개수 K를 입력받고 나면 센서의 좌표를 입력받는다. 문제를 처음 읽었을 때 입력값이 좌표라는 사실을 몰라서 헷갈렸었다.
센서는 직선상의 거리에 쭉 나열되므로 오름차순으로 센서가 나열되어 있다고 생각할 수 있다. 그래서 먼저 입력받은 센서를 오름차순으로 정렬해주었다. 센서를 정렬했다면 집중국을 K개만큼 세워야 하는데, 수신 가능 영역의 길이가 짧아야하므로 집중국을 나누는 기준은 센서와 센서 사이가 가장 먼 지점이 되어야 한다.
가장 먼 센서 사이의 거리 찾기
먼저 각 센서 사이의 차를 구해서 리스트에 담아준다. 문제의 예시 중 하나인 1 6 9 3 6 7로 예를 들면 정렬된 상태는 1 3 6 6 7 9가 된다. 각 센서간의 차는 2 3 0 1 2가 된다. 여기서 가장 많은 차가 발생하는 지점은 3과 6이므로 이 둘을 기준으로 집중국을 세우면 된다. [1, 3]과 [6, 6, 7, 9]로 나누어서 말이다.
이 부분을 코드로 간편하게 표현하기 위해서 각 센서의 차를 오름차순으로 정렬한 뒤, 가장 큰 차이의 값들을 K - 1만큼 빼주는 방법을 사용했다. 집중국에 포함된 센서의 좌표가 N으로 시작해서 N + M의 좌표를 가진 센서까지 포함되어있다고 할 때 수신 가능 영역은 N + M - N이고 이는 N부터 N + M까지 각 차를 더한 값과 같다. 따라서 차이가 가장 큰 값들은 집중국의 수신 가능 영역에 포함되지 않으므로 K - 1만큼 빼고 계산하는 방식으로 집중국의 최소 수신 가능 영역을 구할 수 있다.
Python Code
from sys import stdin
N = int(stdin.readline())
K = int(stdin.readline())
sensor = list(map(int, stdin.readline().split()))
sensor.sort()
diff = [0] * (N - 1)
for i in range(N - 1):
diff[i] = sensor[i + 1] - sensor[i]
diff.sort()
print(sum(diff[:N - K]))참고
