[백준] 1461번 도서관 - C++

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

1461번: 도서관

문제

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

입력

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

출력

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

---

생각한 포인트로는 

1. 시작점이 0 이므로 부호가 다른 지점으로 갈 때는 어차피 0을 거쳐야 하므로 양수와 음수를 따로 저장한다.

2. 한 지점에 도달 했을 때 다시 원점으로 돌아와야 하지만 마지막에는 돌아오지 않고 종료할 수 있으므로 위치의 절댓값이 가장 큰 지점에 책을 놓으며 종료해야 한다.

 

따라서

1. 우선순위 큐에 양수와 음수를 나누어 절댓값으로 저장한다.

2. 두 우선순위 큐의 top에서 큰 수는 한 번만 가면 된다.

    따라서 최소 이동거리(ans)를 0 이 아닌 -큰 수에서 시작하면 모든 지점위치 * 2로 쉽게  이동 거리를 구할 수 있다. 

 3. 양수와 음수 큐 모두 각각 M개 씩 추출해서 ans에 가장 큰 수 * 2 만큼 더한다 

 

---

문제를 보자마자 모든 풀이가 생각난 것은 아니지만 숫자를 나열해 보면서 정리를 하자 규칙성이 쉽게 보였다. 논리 흐름을 작성하고 코드를 작성하니 쉽게 정답을 받을 수 있었다. 다만 블로그 글을 작성하면서 설명하는 글을 잘 못쓴 것 같다!