PS/백준

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

제이온 (Jayon) 2020. 11. 27.

문제

세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 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에서 가장 먼 위치에 있는 책의 위치를 빼야 합니다. 이 값을 빼는 이유는, 이 책을 가장 마지막에 두게 하게끔 조작하기위함입니다.

 

 

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

 

 

소스코드

 

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

댓글

추천 글