[백준/Python] 1461번 : 도서관

문제

https://www.acmicpc.net/problem/1461

1461번: 도서관

---

풀이

m개의 책을 가지고 움직일 때 먼 곳의 값이 이동하는 거리가 된다.
최소 걸음 수를 구하기 위해 0으로 돌아올 필요가 없는 가장 먼 곳을 마지막으로 가야 한다.
가장 먼 곳을 제외한 나머지는 모두 왕복을 하게 된다.

책의 위치가 정수이므로 음수, 양수를 각각 리스트에 저장한다. 
음수는 오름차순 정렬을 하고, 양수는 내림차순 정렬을 한다.

한 번에 m 개씩 옮길 수 있으므로 배열의 길이를 m으로 나눈 만큼 반복한다.
m개의 책을 가지고 이동할 때 움직이는 거리는 리스트의 m*i인덱스이므로 dist배열에 해당 값을 넣어준다.
만약 m으로 나누어 떨어지지 않았다면 dist에 배열의 마지막 묶음 중 절댓값이 큰 값을 넣어준다.
[m * (len(배열) // m]

위 과정을 음수와 양수 똑같이 진행한다.
dist를 오름차순 정렬해서 가장 큰 값을 pop 후 이 값은 도착 지점이므로 ans에 더하고,
나머지 dist 값들은 왕복하므로 곱하기 2를 해서 ans에 더한다.

---

코드

import sys, heapq
input = sys.stdin.readline

n, m = map(int, input().split())
li = [*map(int, input().split())]
minus, plus = [], []
for i in li:
    if i < 0: minus.append(i)
    else: plus.append(i)

dist = []
minus.sort()
for i in range(len(minus) // m):
    dist.append(abs(minus[m * i]))
if len(minus) % m != 0:
    dist.append(abs(minus[m * (len(minus) // m)]))

plus.sort(reverse=True)
for i in range(len(plus) // m):
    dist.append(plus[m * i])
if len(plus) % m != 0:
    dist.append(plus[m * (len(plus) // m)])

ans = 0
dist.sort()
ans = dist.pop()
ans += (sum(dist) * 2)
print(ans)