1461(도서관) - 해결

도서관

 

문제

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

 

입력

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

 

출력

첫째 줄에 정답을 출력한다.

---

처음 생각하였을 때 방법은 일단 정렬을 하고 생각해보았다.

그리고 생각했을 때 M 개씩 어떻게 나누는지가 문제였다.

또한, 마지막은 다시 안 돌아와도 된다고 하였으니 그건 가장 큰 값을 선택하면 된다고 생각을 하였다.

그러면 어떻게 M 개를 나눠야 할까를 생각해 보았다.

그렇게 생각한 것이 양수와 음수를 나누고 절댓값이 큰 수부터 M 개씩 나누는 방식이다.

이렇게 했을 때 어차피 큰 수로 가는 길에 나머지 작은 수를 지나갈 수 있다. 그렇기 때문에 가장 적게 왔다 갔다 하기 위해서는 절댓값이 큰 수부터 나누어야 최대한 적게 왔다 갔다 할 수 있다.

그리고 어차피 음수와 양수를 섞으면 둘 다 왔다 갔다 해야 하기 때문에 나누어서 생각하였다.

그렇게 M 간격으로 넘어가면서 *2씩해서 더한다.

그리고 양수와 음수의 절댓값이 큰 값 중 절댓값이 더 큰 값을 1번만 간다고 정하여 1번 빼준다.

하지만, 양수나 음수가 없다면 한쪽의 절댓값의 최댓값을 1번 빼준다.

import sys
input = sys.stdin.readline

N, M = map(int,input().split())

num_list = list(map(int,input().split()))

# 양수와 음수를 나누어서 저장
plus_list = []
minus_list = []

for i in num_list:
    if i > 0:
        plus_list.append(i)
    else:
        minus_list.append(i)

# 정렬
plus_list.sort(key=lambda x:-x)
minus_list.sort()


total = 0
# 뛰어넘으면서 * 2를 해서 저장
for i in range(0,len(plus_list),M):
    total += plus_list[i] * 2
for i in range(0,len(minus_list),M):
    total += (-minus_list[i]) * 2

# 양수와 음수가 둘다 있다면
# 절댓값이 큰 곳은 1번만 왔다갔다하게
if plus_list and minus_list:
    if plus_list[0] > -minus_list[0]:
        total -= plus_list[0]
    else:
        total += minus_list[0]
# 만약 1쪽만 있을 경우 한쪽의 가장 큰 값을 1번만 왔다갔다
elif plus_list:
    total -= plus_list[0]
else:
    total += minus_list[0]

print(total)