[BOJ] 백준 1461번 도서관 문제 풀이 (Python)

1. 문제 풀이 방법

한 번에 옮길 수 있는 물건의 갯수가 제한이 되어있기 때문에 모든 책을 반납하기 위해서는 왕복을 해야한다. 따라서 멀리 있는 위치일수록 1번만 방문하는 것이 가장 적게 이동하는 것이 되기 때문에 책의 위치를 정렬을 한다음 문제를 풀었다.

1. 책의 위치를 입력받은 이후 음수 위치와 양수 위치로 구분한다
   • 모든 책이 0번 위치에 놓여있기 때문에 음수 위치와 양수 위치를 구분한다.
2. 양수 위치에서 가장 큰 값부터 m개씩 끊어서 move 배열에 담는다
   • move 배열은 한 번 이동할 때 이동해야하는 위치를 담은 배열이다.
   • m개씩 끊는 이유는 멀리 있는 위치에 책을 놓으러 가면서 그보다 가까운 위치에 놓인 다른 책들도 놓을 수 있기 때문이다 (1번 왕복하면서 m개의 책을 동시에 제자리에 둘 수 있다.)
3. 음수 위치에서 가장 작은 값부터 m개씩 끊어서 move 배열에 담는다.
   • 2번 이유와 동일.
4. 가장 먼 위치를 알아내기 위해 move 배열을 절댓값을 기준으로 정렬한다.
   • 가장 먼 위치를 1번만 방문하기 위해 절댓값(거리)을 기준으로 move배열을 정렬한다.
5. 가장 먼 위치는 1번만 방문하고 나머지 위치는 왕복한 거리를 더해서 출력한다.

2. 코드

import sys
def input(): return sys.stdin.readline().rstrip()

n,m = map(int,input().split())
items = sorted(list(map(int,input().split())))
pos = [num for num in items if num > 0] # 양수 위치
neg = [num for num in items if num < 0] # 음수 위치
move = []
for i in range(-1,-len(pos)-1,-m):
    move.append(pos[i])
for i in range(0,len(neg),m):
    move.append(-neg[i])
move.sort(key= lambda x: abs(x))
print(move[-1] + sum(move[:-1]) * 2)