BOJ #13164

---

LEVEL :

Gold5

---

문제 요약 :

각 조들에서 키가 제일 큰사람과 작은사람의 차이의 합이 최소가 되는 조를 형성하여라. 조를 구성하는 인원은 각각 달라도 된다.

---

해결 방안 :

시간이 조금 걸리긴 했지만 스스로 해결 할 수 있었던 문제였다. 이전에 공부했던 문제 중 비슷한 문제가 있었던 것 같다.
일단 정렬된 리스트들에서 인덱스 i 와 i+1의 차이 값들을 저장하는 배열을 만들어 이를 다시한번 정렬 시켰다. N명을 K개의 조로 나누는 것이기에 즉, K-1개의 선으로 N을 나눌 수 있다. 그리고 선이 존재하는 구간에는 구간 간의 차이 값을 구할 필요가 없다

이 개념만 이해하면 큰 무리 없이 정렬에 필요한 O(NlogN) 시간 복잡도로 문제를 해결할 수 있을 것이다.

---

Solution

import sys
input = sys.stdin.readline
if __name__ == "__main__" :
    N,K = map(int,input().strip().split())
    arr = list(map(int,input().strip().split()))
    diff = [[i-1,i,arr[i]-arr[i-1]] for i in range(1,N)]
    diff.sort(key=lambda x : x[2],reverse=True)
    diff = diff[0:K-1]
    diff.sort(key=lambda x : x[1])
    start = 0
    s=0
    for i in range(len(diff)) :
        last = diff[i][1]
        s += (arr[last-1]-arr[start])
        start = last
    s += arr[N-1]-arr[start]
    print(s)

more simple Solution

import sys
input = sys.stdin.readline
if __name__ == "__main__" :
    N,K = map(int,input().strip().split())
    arr = list(map(int,input().strip().split()))
    diff = [arr[i]-arr[i-1] for i in range(1,N)]
    print(sum(sorted(diff)[:N-K]))

개념은 위에 설명한 것과 같다.
K-1개의 분할선을 그을 수있기에
총 N개의 차이값을 저장한 N-1개의 리스트에서 K-1개의 분할 영역을 제외한
(N-1)-(K-1) = N-K index 까지의 차이값들을 더해준다.