13164

날짜 : 2022. 12. 03

사용 언어 : python

 

문제

 

 

코드

import sys

n, k = map(int, sys.stdin.readline().split())
stu = list(map(int, sys.stdin.readline().split()))
stu.sort()
dist = list()
for i in range(1, len(stu)):
    dist.append(stu[i] - stu[i-1])
dist.sort()
res = 0
for i in range(n-k):
    res += dist[i]
print(res)

 

 

풀이

- 조건에 맞게 원생 수와 그룹 개수, 각 학생의 키를 입력받는다.

- 그리고 각 원생들간의 키를 오름차순으로 정렬할 후 왼쪽의 원생과 비교하여 그 차이를 push한다.

- 키차이를 넣은 리스트에서 (n-k)번째까지 더한 후 해당 값을 출력한다.

- 그룹을 만들기 위해 자르는 경우 각 그룹 경계에 있는 키차이는 저절로 사라진다.

- 예를 들어 5개 그룹을 만들기 위해서는 전체에서 4번 잘라야 한다. 이를통해 4번 자름으로써 사라지는 수는 가장 큰 키차이를 보이는 수여야 하며 이는 위의 그림에서도 알 수 있다.

(차이가 같은 경우는 다양한 경우의 수로 간주한다.)

 

 

알게된 점

- 

 

 

참고 사이트

-