[99클럽/파이썬 챌린저/11일차] 도서관

백준 1461번 도서관 G4

 

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

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

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

 

 

그리디 알고리즘, 정렬

 

음수 혹은 양수 방향에서 가장 가까운 책 m권을 먼저 가져다 놓으면 되는 탐욕 알고리즘이다.

다시 0으로 이동할 필요가 없으므로, 가장 먼 책을 마지막에 가져다 둔다.

 

정렬 이후에 음수와 양수를 따로 처리하였다.

 

 

import sys

bookNum , takeNum = map(int, sys.stdin.readline().split())

arr = list(map(int, sys.stdin.readline().split()))
arr.sort()
foot = 0

arrPlus = list(filter(lambda x:x > 0, arr))
arrMinus = list(filter(lambda x:x < 0, arr))


if arr[0] < 0 and arr[-1] > 0:
    if abs(arr[0]) < abs(arr[-1]):
        foot = -arr[-1]
    else:
        foot = arr[0]
else:
    if arr[0] < 0:
        foot = arr[0]
    else:
        foot = -arr[-1]

temp = 0


while len(arrPlus) > 0:
    foot += 2 * arrPlus[-1]
    for i in range(takeNum):
        if len(arrPlus) > 0:
            arrPlus.remove(arrPlus[-1])


while len(arrMinus) > 0:
    foot -= 2 * arrMinus[0]
    for i in range(takeNum):
        if len(arrMinus) > 0:
            arrMinus.remove(arrMinus[0])
    
print(foot)

 

---

 

 

그리디 알고리즘이라 그런가, 이전에 구현한 코드가 문제가 많은데도 N과 M이 작아서 통과된다.