[Python] 백준 1461 도서관

 

문제

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

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

 

 

 

 

 

 

 

난이도

골드4

 

 

 

 

 

 

내 코드

import sys

n, m = map(int,sys.stdin.readline().split())
book = [0] + list(map(int,sys.stdin.readline().split()))
book.sort()
home_index = -1
answer = 0
for i in range(n+1) :
    if book[i] == 0 :
        home_index = i
        break

left_index = m
while left_index < home_index :
    answer += (-book[left_index] * 2)
    left_index += m

right_index = n - m
while home_index < right_index :
    answer += (book[right_index] * 2)
    right_index -= m

if -book[0] < book[n] :
    answer += (-book[0] * 2 + book[n])
else :
    answer += (book[n] * 2 + -book[0])

print(answer)

 

 

 

 

풀이과정

이 문제는 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다.   는 문장이 중요하다.

마지막으로 정리할 책을 왼쪽 끝과 오른쪽 끝 중에 어디로 하는게 효율적인지 따지면 된다.

우선 왼쪽과 오른쪽 모두 왕복을 여러번 해야할 경우에는 while 문을 통해 미리 걸음 수를 더했다. 

마지막으로 왼쪽이나 오른쪽 끝으로 가기 때문에 끝에서 m번째 까지는 제외하고 왕복 걸음수를 더한것이다.

 

그 후 왼쪽이 멀면 오른쪽을 다녀와서 왼쪽에서 끝내고, 오른쪽이 멀면 왼쪽을 다녀와서 오른쪽에서 끝내도록 하여 문제를 해결했다.