문제 요약 및 풀이
처음에 문제 지문을 보고 이해가 안 갔다.
아래와 같이 바꿀 수 있지 않을까?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
## 문제
한국도로공사는 고속도로의 유비쿼터스화를 위해 일직선의 고속도로 위에 N개의 센서를 설치하였다.
이 센서들로부터 자료를 모으고 분석할 몇 개의 집중국을 세우려 하지만, 예산상의 문제로 고속도로 위에 최대 K개의 집중국을 세울 수 있다.
각 집중국은 센서와 통신할 수 있는 영역, 센서 수신 가능 영역 자유롭게 조절할 수 있으며, 수신 가능 영역 길이는 0 이상인 연결된 구간으로 나타낼 수 있다.
N개의 센서는 모두 적어도 하나의 집중국과 통신해야 하지만, 집중군의 유지비 문제로 각 집중국의 수신 가능 영역 길이의 합을 최소화해야 한다.
## 입력
첫째줄에 센서의 개수 N, 둘째줄에 설치할 수 있는 집중국의 개수 K가 주어진다.
셋째줄에는 고속도로에 설치된 N개의 센선의 좌표가 한 개의 정수로 주어진다.(단, 좌표의 절대값은 1,000,000 이하이며, 같은 위치에 설치된 센서가 있을 수 있다.)
## 출력
각 집중국의 수신 가능 영역 거리의 합의 최솟갑을 출력한다.
## 예제 입력
6
2
1 6 9 3 6 7
## 예제 출력
5
## 예제 설명
센서가 순서대로 좌표 1, 3, 6, 6, 7, 9에 설치되어있다.
[1, 3], [6, 9] 영역을 수신 가능 영역으로 설정한 2개의 집중국을 세우면, 수신 가능 영역 길이의 합이 5로 최소이다.
(어떻게 가공을 하려고 해도 문제 설명이 어색한 것 같다;;)
이제, 풀이를 살펴보자.
센서의 개수가 총 N개이다. 따라서, 센서 사이 구간은 총 N-1개이다.
집중국의 개수는 최대 K 개이다. 따라서, 집중국을 세워서 만들 수 있는 구간은 총 K개이다.
근데, 다르게 말해서, N-1개의 센서 사이 구간들 중, K-1개의 구간을 삭제할 수 있다는 이야기가 된다.
따라서, N-1개의 센서 사이 구간의 길이를 쭉 나열해두고, 정렬해서 최대 K-1개의 구간을 날리고, 길이의 합을 구하면 된다.
풀이 코드
1
2
3
4
5
6
7
8
9
n = int(input())
k = int(input())
sensors = sorted(list([*map(int,input().split())]))
diffs = sorted([sensors[i] - sensors[i-1] for i in range(1,len(sensors))])
print(sum(diffs[:(len(diffs) if k == 1 else 1 - k)]))