[백준 1461번] 도서관 - java

문제 설명

1. N권의 책, 한번에 들수있는 양 M이 주어진다.

2. 현재 위치 0으로부터 해당 책이 들어가야하는 위치가 N개 주어진다.

3. 모든 책을 원래 위치에 가져다 놓는 최소 거리를 구하라.

4. 마지막 책을 가져다가 두면 더이상 0위치로 돌아올 필요는 없다.

 

풀이 과정

 1. 그리디 문제이고, 문제 풀이를 떠올리는것은 힘들지만 구현은 쉬운 문제이다.

 2. 중요한 것은 거리가 +, - 두 가지로 주어진다는 것이고, 0의 위치를 지나가기 때문에 각각의 이동이 따로따로 행해져야 한다는 것이다.

 3. 그리고 어느 쪽이든 가장 먼곳까지 갔다가 돌아오면 된다.

 4. 마지막 책을 갖다 놓았을 때 더이상 0의 위치로 돌아올 필요는 없으니, 가장 먼곳에 마지막으로 책을 가져다 두면 될것이다.

---

 5. (2)번의 문제에서 먼 거리부터 재어주는 우선순위 큐를 두개 만들어준다. 참고로 음수로 가는 우선순위 큐는 값을 절대값으로 넣어주어야 할것이다.

 6. 두 우선순위 큐 중 더 먼 거리를 구해서 일단 따로 보관해준다.

 7. 이제 N개의 책을 들고 가장 먼 위치로 가면 된다. 그러면

가장 먼 위치 구하기

가장 먼 위치까지 가면서 책 하나씩 꽂아주기

가장 먼 위치에서 돌아오기

이렇게 된다.

 8. 내림차순 우선순위 큐이기 때문에 peek*2로 왔다갔다 하고 책은 M개 들고가면 된다.

코드