[BOJ] 백준 1461번 : 도서관 (JAVA)

문제

세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다.

 

각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다.

 

 

입력

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

 

 

출력

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

 

 

풀이

그리디 알고리즘을 활용하여 풀 수 있는 문제였습니다.

 

 

정리되어 있지 않은 책을 들고 원래 있던 자리에 모두 갖다 놓아야하는데, 이때 최소 이동 거리를 구해야했습니다.

 

처음 생각할 수 있는 로직은 거리가 가까이 있는 M권의 책을 들고 이동하는 것입니다.

 

다만, 문제의 예시에서 알 수 있듯이, M이 2이고, 음수 위치에 있는 책들이 [-39, -37, -29, -28, -6] 이라면 예외가 생깁니다. 위의 로직을 따르면 (-6, -28), (-29, -37), (-39)를 가져갈텐데, 이것보다 (-6), (-28, -29), (-37, -39) 순서로 책을 가져가는 것이 더 이동거리가 짧습니다.

 

따라서, 거리가 멀리 있는 M권의 책을 들고 이동해야 합니다. 

 

 

하지만, 음의 위치에 있는 책과 양의 위치에 있는 책을 동시에 들고 가면 어차피 한 권을 꽂고, 나머지 한 권을 꽂으려고 하면 원래 0 위치에 다시 오게 됩니다.

 

따라서, 음의 위치에 있는 책을 담는 우선 순위 큐와 양의 위치에 있는 책을 담는 우선 순위 큐 2개를 정의하면 됩니다. 이때, 정렬 기준은 절댓값 위치에 대해 내림차순 정렬하면 됩니다.

 

그리고 (맨 꼭대기에 있는 값) x 2를 이동 거리로 취하고, M권의 책을 poll합니다. 이렇게 하면, 최소 이동 거리를 구할 수 있는데 한 가지 주의해야 합니다.

 

모든 책을 가져다 놨으면 원래 0 위치로 돌아올 필요가 없으므로, ans에서 가장 먼 위치에 있는 책의 위치를 빼야 합니다. 이 값을 빼는 이유는, 이 책을 가장 마지막에 두게 하게끔 조작하기위함입니다.

 

 

아래는 위 과정을 정리한 소스코드입니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.