-문제:https://www.acmicpc.net/problem/2212

n개의 구간을 k개의 영역으로 나누면 된다고 생각했고, 각 위치의 차이를 이용하는 것이라고 생각했는데 

그 다음 구현을 어떻게 할지 몰랐던 문제다

-정답풀이:

기지국이 세션수보다 같거나 크면 모든 지점에 기지국 설치하면 되므로 0을 출력한다

먼저 세션 위치를 다 받아서 작은 것부터 정렬한다

sys.exit()를 빼고 돌렸더니 틀렸다. 

0이 출력되고 끝나야하므로 exit()를 선언해줘야 하는 것 같다

인접한 세션끼리의 거리차를 distance 리스트에 넣는다

거리차를 내림차순으로 정렬한 뒤 거리가 가장 긴 것부터 k-1개를 제거하고 남은 길이의 합을 구하면 된다

 

import sys
n=int(input())
k=int(input())
s=sorted(list(map(int,input().split())))

if k>=n:
    print(0)
    sys.exit()
    
distance=[]
for i in range(1,n):
    distance.append(s[i]-s[i-1])
    
distance.sort(reverse=True)
for _ in range(k-1):
    distance.pop(0)
print(sum(distance))

+ Recent posts