문제 설명

세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다.

입력 조건

첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 책의 위치는 0이 아니며, 절댓값은 10,000보다 작거나 같은 정수이다.

전체 코드

n, m = list(map(int, input().split()))
arr = list(map(int, input().split()))

answer = 0

# 양수와 음수로 나눈다.
positive = []
negative = []

for elem in arr:
    if elem > 0:
        positive.append(elem)
    else:
        negative.append(elem)
# 양수 배열은 내림차순, 음수 배열은 오름차순으로 정렬
positive.sort(reverse=True)
negative.sort()

distance = []

i = 0
while i < len(positive):
    max_value = positive[i]
    # m개 단위로 나누어서 가장 큰 값 가져오기
    for j in range(i, i + m):
        if j >= len(positive):
            break
        max_value = max(max_value, positive[j])
    distance.append(max_value)
    i += m

i = 0
while i < len(negative):
    min_value = negative[i]
    # m개 단위로 나누어서 가장 작은 값 가져오기
    for j in range(i, i + m):
        if j >= len(negative):
            break
        min_value = min(min_value, negative[j])
    distance.append(abs(min_value))
    i += m

# 절댓값순으로 오름차순 정렬
distance.sort()

# 절댓값이 가장 큰것을 제외하고 나머지는 0을 경유해야하므로 *2
for i in range(len(distance) - 1):
    answer += (distance[i]) * 2

# 절댓값이 가장 큰 것은 0을 경유하지 말고 진행해야 최소거리를 할 수 있다.
answer += distance[-1]
print(answer)

해설

n=3, m=2, 책의 위치=[1,3,-2]라 하자.

일단, 정답은 abs(-2) x 2 +3(==max(1,3)) = 5이다.
양수와 음수를 따로 나눠서 절댓값이 큰 대로 택한다면 위와 같은 결과과 나온다.

반면, 단순히 절댓값이 큰대로만 택하면 (1,-2)와 3을 택하게 되는데, 이때는 1 x 2 + abs(-2) * 2 + 3 = 2+4+3=9가 나온다.

이러한 결과가 나오는 이유는 양수, 음수를 번갈아 이동하게 되면 0을 지나치게 되기 때문이다.
반면 음수, 양수대로 따로 나눠서 택하면 0을 중간에 지나치지 않는다.

정리해보면
1. 0을 중간에 지나치지 않기 위해 양수, 음수를 나눠서 절댓값순으로 택해야 한다.
2. 마지막에는 돌아올 필요가 없으므로 절댓값이 제일 큰 값은 x2 하지 않게 계산한다.