악곱 == 악성곱슬

그리디

---

해당 문제를 그리디로 접근한 정당성은 다음과 같다.

• 고속도로에 집중국의 위치를 최적화 하는 것인데 고속도로가 1자평면에 있는 점 → 그냥 정렬해서 거리가 가장 긴 도로를 하나씩 배제하면 되겠다 → 가장 긴 도로부터 배제한다(그리디)

위 아이디어에 대한 코드는 아래와 같다.

import sys

def solution(sensors, n, k):
    answer = 0
    sensors.sort()
    dist = list()
    for i in range(1, n):
        dist.append(sensors[i] - sensors[i - 1])
    dist.sort()
    answer = sum(dist[0:n-k])
    return answer

if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())
    K = int(sys.stdin.readline().rstrip())
    _sensors = list(map(int, sys.stdin.readline().rstrip().split()))
    print(solution(_sensors, N, K))