[백준/1461] 도서관 (Python)

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

1461번: 도서관

 

Difficulty : Gold 5

 

Status : Solved

 

Time : 00:06:15

 

---

 

문제 설명

 

 

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

 

 

입력 및 출력

 

입력

 

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

 

출력

 

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

 

입력 예시

 

7 2
-37 2 -6 -39 -29 11 -28

 

출력 예시

 

131

 

 

---

 

풀이

 

그리디하게 생각해 볼 수 있다. 

 

• 우선, 0을 기준으로 두 구역으로 나뉘므로 양수는 양수끼리, 음수는 음수끼리 그룹화하자. 이동 시 같은 구역의 책을 우선적으로 옮기는 게 동선이 가장 짧다.
• 한 구역의 책을 옮길 때, 총 편도 이동거리는 M개의 책 중 가장 거리가 먼 책의 거리가 된다. 즉 최대 거리의 책 하나를 선정하고, 그 최대 거리와 가까운 책들을 옮기는 게 동선이 가장 짧다. 이를 위해서 정렬이 필요하다. 이 때 원점으로 다시 돌아오는 왕복 거리는 가장 거리가 먼 책의 거리 * 2 가 된다.
• 조건 '책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다'를 생각해보자. 두 구역 중 가장 최대 거리인 책을 운반할 때, 편도로 운반하는 것이 가장 동선이 짧아질 것이다. 

이들을 고려하여 단계적으로 탐색하면 풀이 가능하다!

 

풀이 코드

N, M = map(int, input().split())
book_list = list(map(int, input().split()))
pos_sector, neg_sector = [0], [0]
for num in book_list :
  if num > 0 :
    pos_sector.append(num)
  else :
    neg_sector.append(-num)

pos_sector.sort()
neg_sector.sort()
max_val = max(pos_sector[-1], neg_sector[-1])
result = 0

while pos_sector :
  result += pos_sector[-1] * 2
  cnt = 0
  while pos_sector and cnt < M :
    cnt += 1
    pos_sector.pop()

while neg_sector :
  result += neg_sector[-1] * 2
  cnt = 0
  while neg_sector and cnt < M :
    cnt += 1
    neg_sector.pop()

print(result - max_val)

풀이 완료!