[Python] 백준 1461 & 백준 2212

# 백준 1461 도서관
# 탐욕 알고리즘

# 음수와 양수에 대해여 개별적으로, m개씩 묶어서 처리

import heapq
# heapq는 음수도 인식하기때문에 가장 큰 마이너스값, 즉 가장 작은값을 구하기위해 모든 원소를 마이너스로 바꿔준다.

n, m = map(int, input().split(' '))
array = list(map(int, input().split(' ')))
positive = []
negative = []

# 가장 거리가 먼 책의 위치찾기
farest = max(max(array), -min(array))

for i in array:
    # 책의 위치가 양수인 경우
    if i > 0:
        heapq.heappush(positive, -i)
    # 책의 위치가 음수인경우
    else:
        heapq.heappush(negative, i)

result = 0
while positive:
    # 한번에 m개씩 옮길수 있으므로 m개씩 빼낸다
    result += heapq.heappop(positive)
    for _ in range(m-1): # #나머지도 뽑는다
        if positive:
            heapq.heappop(positive)

while negative:
    result += heapq.heappop(negative)
    for _ in range(m-1):
        heapq.heappop(negative)

#왕복거리를 계산해야되기때문에 *2 해주지만 가장 먼곳은 편도로 계산해야하니깐 한번 빼준다
print(-result * 2 - farest)

# 백준 2212
import sys
n = int(input())
k = int(input())

# 집중국의 개수가 n이상일때
if k >= n:
    print(0)
    sys.exit()

# 모든 센서의 위치를 입력받아 오름차순 정렬
array = list(map(int, input().split(' ')))
array.sort()

# 센서간 거리의 내림차 정렬
distances = []
for i in range(1, n):
    distances.append(array[i] - array[i -1] )
    distances.sort(reverse = True)

# 가장 긴 거리부터 하나씩 제거
for i in range(k - 1):
    # 거리를 0 으로 만듦으로써 제거. 이걸 k -1 만큼 반복
    distances[i] = 0
print(sum(distances))