[백준 1461] 도서관(python)

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

1461번: 도서관

도서관 문제

0의 위치에서 놓여있는 책들을 m개 들어서 꽂으러 이동할 때 걸리는 최소 시간을 구하는 문제

그리디 개념과 정렬 개념을 활용하여 해결할 수 있었다.

📌 문제 접근 포인트

1. 책을 들고 0의 지점에서 M개를 들고 꽂으러 이동하러 다녀야 한다. 즉, 책을 꽂고 다시 0으로 돌아와야 하니 2배의 거리만큼 이동해야 한다 단, 마지막 이동을 할 때는 제자리를 돌아올 필요가 없으니 1번만 이동해도 된다.
2. 단순히 생각했을 때, 가장 먼지점 기준으로 M개씩 잘라서 꽂을 수 있도록 맞춰주면 된다.
3. 양수와 음수로 나뉘어져 있으므로, 양수와 음수를 한 번에 고려하기보단 따로 고려하면 계산하기 좋다. 양수와 음수를 기준으로 리스트를 나눠주고, 어차피 계산할 때 양수로 해야 하니, 미리 양수로 바꿔서 나눠주자.
4. 각 리스트를 정렬하고, 1번에서 생각한 개념을 적용하고, 마지막에 최대 값을 1번만 고려할 수 있도록 코드를 구현해주자.

⚙ 내가 푼 정답 코드

def move(arr,a): # 둘다 같은 방법으로 탐색
    arr.sort(reverse = True) # 그리디하게 정렬
    for i in range(a//M):
        distance.append(arr[i*M])
    if a % M:
        distance.append(arr[(a//M)*M])

import sys
N, M = map(int, sys.stdin.readline().split())
nums = list(map(int,sys.stdin.readline().split()))
minus, plus = [], []
distance = [] # 거리 지정
for i in nums: # 양수부분 음수부분 나누기
    if i > 0:
        plus.append(i)
    else: 
        minus.append(abs(i)) #음수수분 양수처리

move(plus,len(plus))
move(minus,len(minus))

distance.sort()
result = distance.pop() + 2*sum(distance) # 최대부분은 1번만 계산하고 나머지 2배