[백준 1461 🥇] 도서관

문제

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

입력

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

출력

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

문제 풀이

import sys
from collections import deque

n,m=map(int, sys.stdin.readline().strip().split(' '))
books=list(map(int, sys.stdin.readline().strip().split(' ')))

books.sort()

# 절댓값이 가장 큰 인덱스가 양수인지 음수인지?
maxidx=0
if abs(books[-1])>abs(books[0]):
    maxidx=-1

plus=deque()
minus=deque()
for book in books:
    if book>0:
        plus.append(book)
    else:
        minus.append(book)

# 음수 영역 기준 최소 발자국 구하기
ans_minus=0
mod_minus=len(minus)%m
step=0
if minus and len(minus)<=m:
    if minus[0]==books[maxidx]:
        ans_minus+=abs(minus[0])
    else:
        ans_minus+=abs(minus[0])*2
else:
    if mod_minus != 0:
        for _ in range(mod_minus):
            step = minus.pop()
        ans_minus += (abs(step) * 2)

    while minus:
        if len(minus) <= m:
            if minus[0] == books[maxidx]:
                ans_minus += abs(minus[0])
                break
        for _ in range(m):
            step = minus.pop()
        ans_minus += (abs(step) * 2)

# 양수 영역 기준 최소 발자국 구하기
ans_plus=0
mod_plus=len(plus)%m
step=0
if plus and len(plus)<=m:
    if plus[-1]==books[maxidx]:
        ans_plus+=plus[-1]
    else:
        ans_plus+=plus[-1]*2
else:
    if mod_plus != 0:
        for _ in range(mod_plus):
            step = plus.popleft()
        ans_plus += (step * 2)

    while plus:
        if len(plus) <= m:
            if plus[-1] == books[maxidx]:
                ans_plus += plus[-1]
                break
        for _ in range(m):
            step = plus.popleft()
        ans_plus += (step * 2)

print(ans_plus+ans_minus)

• 책을 모두 제자리에 둔 이후에 다시 0으로 돌아올 필요가 없으므로, 절댓값이 가장 큰 위치에 있는 책은 마지막에 처리해서 다시 돌아오는 걸음은 추가해주지 않아야 한다.
• 우선 입력받은 책들의 위치를 정렬해준다.
• 절댓값이 큰 수가 가장 왼쪽 수인지, 가장 오른쪽 수인지 비교하고, 결과를 maxidx에 0(왼쪽) 또는 -1(오른쪽)으로 저장해준다.
• 마지막 책을 가져다 둔 경우를 제외하고 책을 가져다 놓고 다시 0으로 돌아와야 하기 때문에 0을 중심으로 수들을 살펴보면서 음수인 값들을 따로 저장하고, 양수인 값들을 따로 저장해서 각각 최소 걸음을 구하고 더하면 된다.
• 음수와 양수 각각의 개수가 m으로 나눠지지 않는 경우, m으로 나눈 나머지만큼은 가장 거리가 가까운 순서대로 처리해주고, 남은 책들을 한 번에 처리할 수 있는 m권씩 제거해주면서 몇 걸음을 다녀와야 하는지 계산한다.

문제 예제 1,2,3번을 기준으로 예시를 들어보면 다음과 같다.