이번 문제는 원생들의 키를 모두 입력 받은 뒤에 각 원생들 간의 키 차이를 따로 저장하여 이를 내림차순 정렬하고 k-1번째 키 차이부터 가장 마지막의 키 차이까지의 합을 출력하여 해결하였다.

첫 시도에는 k번 반복하는 반복문으로 키 차이 배열에서 원소를 삭제하는 방식으로 제출하였는데 시간초과가 발생하였고 원소 삭제 대신 파이썬의 슬라이싱을 이용하여 반복문 하나를 줄여 시간 제한 안에 돌아가는 코드를 완성하였다.

• n과 k를 입력받는다.
• 원생들의 키를 저장할 배열 child를 선언하고 원생들의 키를 입력받는다. 원생들의 키는 문제의 조건에 따라 오름차순으로 입력된다.
• 원생들의 키 차이를 저장하는 배열 gap을 선언하고 원생들의 키 차이를 저장한다.
• gap을 내림차순 정렬한다.
• gap[k-1:]의 합을 출력한다.

Code

n, k=map(int, input().split())
child=list(map(int, input().split()))
gap=[child[i]-child[i-1] for i in range(1, n)]
gap.sort(reverse=True)
print(sum(gap[k-1:]))