https://www.acmicpc.net/problem/2212
2212번: 센서
첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있
www.acmicpc.net
import sys
if __name__ == '__main__':
N = int(input())
K = int(input())
S = list(map(int, sys.stdin.readline().rstrip().split()))
S.sort()
distance = []
for i in range(1, N):
distance.append(S[i] - S[i-1])
distance.sort(reverse=True)
print(sum(distance[K-1:]))
문제를 이해하기까지 오래걸렸다.
문제 이해 후, 2시간 넘게 고민하였음에도 핵심 아이디어가 떠오르지 않아 결국 풀이를 참고했다.
핵심아이디어만 생각할 수 있다면 풀이 자체는 매우 쉽다.
이 문제는 기지국의 수만큼 센서를 Grouping 하여 각 Group 의 구간의 합이 최소가 되면 된다.
풀이:
1. 우선 뒤죽박죽인 센서를 위치 순으로 정렬
2. 각 센서간의 거리를 구하여 리스트에 저장한 후, 내림 차 순 정렬한다.
3. 거리가 최대인 것을 K-1 개 만큼 제외한 후, 나머지 거리의 합계가 정답이다.
3에서 거리가 최대인 것을 K-1 개 만큼 제외하는 이유는 아래 사진을 보고 가장 잘 이해가 되었다.
위 이미지의 경우 K = 2, 즉 기지국이 2개인 경우로 기지국을 두개 설치하면 3과 6 사이의 거리는 제외 시켜도 된다.
기지국이 5인 경우(K=5) 각 센서를 5 묶음으로 나누면 위와 같은 원리로 제외 시켜도 되는 거리가 4(K-1) 개 발생하며
이 제외시켜도 되는 거리를 최대 거리를 제외시킴으로써 최소 거리를 구할 수 있는 것이다.
ㅁ <-제외해도 되는 거리-> ㅁ <-제외해도 되는 거리-> ㅁ <-제외해도 되는 거리-> ㅁ <-제외해도 되는 거리-> ㅁ