99클럽 코테 스터디 18일차 TIL + 그리디

https://www.acmicpc.net/problem/2212

import sys
input = sys.stdin.readline

n = int(input())
k = int(input())
ls = list(map(int, input().split()))

ls.sort()
dist = []
for i in range(n-1):
    dist.append(ls[i+1] - ls[i])


dist.sort()
print(sum(dist[:n-k]))

• 코드는 매우 간단해 보이지만 문제를 이해하는데 너무 오래걸렸다......
• n개의 센서로 최대 k개의 집중국을 만들어야 한다.

• 그림과 같이 최대 2개의 집중국을 만들 수 있고, 그 거리를 최소로 하려면 가장 거리 차이가 많이 나는 3과 6사이를 끊어 집중국을 나누어야 한다.
• 우선 센서를 오름차순 정렬을 한 후에 각 센서마다의 거리차이를 나타내는 배열 dist를 구한다.
• 그 후, 가장 차이가 많이 나는 값을 빼주어야 하기 때문에 거리배열도 오름차순 정렬을 한다.
  • 이 때, 2개의 집중국을 만들기 위해선 가장 거리차이가 많이 나는 1개를 빼주어야 하고.
  • 3개의 집중국을 만들기 위해선 2번을 빼주면된다.
  • 즉, k 개의 집중국을 만들기 위해선 k-1번을 빼주면 되는데 거리배열은 n-1개 값을 갖고 있고 그 중 k-1개를 빼주어야 하므로 n - 1 - (k - 1) = n - k 가 된다.
• 거리차이 배열에서 차이가 많이 나는 값을 k-1개 뺀 값의 합을 구하면 최소값을 구할 수 있다.
  • 즉, dist배열의 n-k개의 합이 집중국의 수신 가능 영역의 길이의 합의 최솟값이다.