백준 1461번: 도서관

백준 1461번: 도서관

 

 

- 정렬과 그리디 알고리즘을 활용한다.

 

- 예제로 나온

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

를 살펴보자.

 

•  좌표를 음수와 양수로 나누어 서로 다른 LinkedList에 저장한다.

•  LinkedList를 내림차순으로 정렬하면 위의 사진처럼 될 것이다.
• (-39) 좌표는 원점으로부터 제일 먼 곳이므로 제일 마지막에 가야 된다. 왜냐하면 마지막에는 책을 가져다 놓고 다시 원점으로 돌아올 필요가 없기 때문이다. 따라서 두 LinkedList의 0번째 인덱스의 값을 비교하여 절댓값이 더 큰 좌표는 편도 거리만 계산한다. 이 때 -39에 가면서 -37에 들렸다가 가야 된다. 따라서 해당 LinkedList(여기서는 A LinkedList)를 m-1번 poll() 해 준다. 그러면 아래의 그림과 같이 LinkedList가 변할 것이다.

• 이후로는 LinkedList의 0번째 인덱스 값을 poll() 한 뒤 왕복 거리이므로 x2 한 값을 더한 뒤, m - 1번의 poll()를 해주면 된다. 이 과정을 두 LinkedList의 size가 0이 될 때까지 하면 된다. 예제에서는 (29 * 2) + (6 * 2) + (11 * 2) 를 하게 된다.

 

※ 음수인 좌표의 경우 초기에 LinkedList에 저장할 때, (-)을 붙여 양수로 만든 뒤 저장하면 이후 계산에서 훨씬 수월하다. 또한 poll()과 peek()의 경우 아무 값이 저장이 되어 있지 않으면 NULL 값을 반환하기 때문에 LinkedList가 비어있는 경우와 아닌 경우를 미리 나누어 생각하면 좋다.