IT-garden

문제

한국도로공사는 고속도로의 유비쿼터스화를 위해 고속도로 위에 N개의 센서를 설치하였다. 문제는 이 센서들이 수집한 자료들을 모으고 분석할 몇 개의 집중국을 세우는 일인데, 예산상의 문제로, 고속도로 위에 최대 K개의 집중국을 세울 수 있다고 한다.

각 집중국은 센서의 수신 가능 영역을 조절할 수 있다. 집중국의 수신 가능 영역은 고속도로 상에서 연결된 구간으로 나타나게 된다. N개의 센서가 적어도 하나의 집중국과는 통신이 가능해야 하며, 집중국의 유지비 문제로 인해 각 집중국의 수신 가능 영역의 길이의 합을 최소화해야 한다.

편의를 위해 고속도로는 평면상의 직선이라고 가정하고, 센서들은 이 직선 위의 한 기점인 원점으로부터의 정수 거리의 위치에 놓여 있다고 하자. 따라서, 각 센서의 좌표는 정수 하나로 표현된다. 이 상황에서 각 집중국의 수신 가능영역의 거리의 합의 최솟값을 구하는 프로그램을 작성하시오. 단, 집중국의 수신 가능영역의 길이는 0 이상이며 모든 센서의 좌표가 다를 필요는 없다.

입력

첫째 줄에 센서의 개수 N(1<=N<=10,000), 둘째 줄에 집중국의 개수 K(1<=K<=1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 이상 있으며, 좌표의 절댓값은 1,000,000 이하이다.

출력

첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.

예제 입력과 출력

알고리즘 분류

그리디 알고리즘

정답

import sys

n=sys.stdin.readline().strip()
k=int(sys.stdin.readline().strip())
a=list(map(int,sys.stdin.readline().split()))

b=sorted(a)
c=[]

for i in range(1,len(a)):
    c.append(b[i]-b[i-1])

c.sort()

for j in range(k-1):
    if len(c) == 0:
        c.append(0)
        break
    else:
        c.pop()
    
print(sum(c))

*리스트를 정렬하고 i 요소에서 i-1요소의 값을 빼줘 새로운 리스트에 저장합니다.

새로운 리스트에서 가장 큰 값부터 기지국 수 - 1 만큼 삭제하고 합을 계산합니다.

1 3 6 6 7 9

 2 3 0 1 2

2, 3, 0, 1, 2를 0, 1, 2, 2, 3으로 정렬하고 기지국 수(2)-1 만큼 삭제합니다.

0, 1, 2, 2의 합은 5로 집중국의 수신 가능 영역의 길이의 합의 최솟값입니다.

백준 알고리즘 2212번 : www.acmicpc.net/problem/2212