세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다.
7 2
-37 2 -6 -39 -29 11 -28
첫째 줄에 정답을 출력한다.
131
우선 책들이 0에 있으므로, 마지막을 제외하고서는 M권을 가져다 놓고 다시 0으로 돌아와야 합니다.
즉, 단 한번은 편도로 이동이 가능합니다. 최소로 걸음하기 위해서 이 편도를 가장 먼 거리로 사용해야 합니다. 따라서, 절대값이 가장 큰 값을 마지막으로 하여, 가장 먼 곳에서 끝내고 돌아오지 않는 경우가 최소로 걸음하는 경우입니다.
나머지의 경우는 왕복으로 이동해야 하므로, 각 걸음마다 가장 먼 거리 * 2 만큼 걸음합니다. 즉, 매 순간 최선의 선택인 최대한 먼 곳에 가서 M권을 모두 처리하고 돌아오는 방식을 택합니다.
만약 먼 곳부터 처리하지 않으면, 멀리 두 번 가야하는 비효율이 생깁니다. 또 한 번에 최대한 많이 책을 가져다 놓아야 왕복 횟수를 최소화해서 거리를 최소화할 수 있습니다. 이 두 가지 선택 조건이 최선의 판단이고 이러한 전략이 그리드입니다.
이에 따라 구현해보겠습니다.
우선, 그리디를 위한 전처리로 거리 순으로 위치를 정렬해야 합니다. 책 위치를 음수값과 양수값으로 나눕니다. 이유는 입력 예를 들어 설명하겠습니다.
// 우선 위치를 오름차순으로 정렬해 보겠습니다. [-39, -37, -29, -28, -6, 2, 11]
const locations = input[1].split(' ').map(Number).sort((a, b) => a - b);
가장 먼 거리의 편도 처리를 생각하지 않고, 위치 순서대로 다녀오면 다음과 같습니다.
위치를 오름차순으로 정렬해서 2권씩 놓고 온다고 했을 때, -6 부분에서는 2권을 가져다 놓을 수 없습니다. 다음 책 위치인 2 는 양수로 바뀌므로 0을 지나 2를 새로 가야합니다. 이를 고려하기 위해 위치를 음수값과 양수값으로 나누어 생각합니다.
이 때, 음수는 오름차순으로, 양수는 내림차순으로 정렬해야 가장 먼 걸음 순으로 정렬됩니다.