1461 도서관

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

1461번: 도서관

---

효율적인 동선을 짜는 문제인데, 들고 다닐 수 있는 책의 개수가 한정되어 있다.

 

모든 책이 0위치에 있기 때문에 들고 있는 책 정리를 끝냈다면 다시 0으로 돌아와야 한다. 

 

어차피 돌아와야 한다면 책을 정리하러 갔다가 오는 동선에 다른 책들을 정리하면 효율적인 동선이 된다.

 

따라서 제일 먼 거리를 갔다가 오면서 들고 있는 책들을 정리하게 된다.

 

책의 위치가 음수일 수도 있으므로 책의 위치를 양수와 음수로 나누어 따로 정리하면 동선을 더 줄일 수 있다. 

 

책들을 오름차순으로 정리한 다음, 양수 위치의 책들을 M개씩 정리하면서 제일 먼 거리 * 2만큼 이동 거리에 누적한다.

음수 위치의 책들도 마찬가지이다.

 

그런데 모든 책의 정리를 끝냈다면 0으로 돌아오지 않는다고 하니, 마지막 동선이 제일 먼 거리의 책이라면 편도로만 가면 되기 때문에 이 점을 생각해야한다.

 

앞서 이동 거리를 누적시킬 때 제일 먼 거리가 왕복으로 계산되었기 때문에 이동 거리에서 제일 먼 거리를 빼주면 편도로 간 셈이 된다.

---

#include <iostream>
#define ABS(X) ((X) > 0 ? (X) : -(X))
int main() {
  int N, M, arr[50]{0}, positiveStartIndex = 0;
  scanf("%d %d", &N, &M);
  for (int i = 0; i < N; i++) {
    scanf("%d", &arr[i]);
    if (arr[i] < 0) {
      positiveStartIndex++;
    }
  }
  for (int i = 0; i < N - 1; i++) {
    for (int j = i + 1; j < N; j++) {
      if (arr[i] > arr[j]) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }
    }
  }
  int dist = 0;
  for (int i = N - 1; i >= positiveStartIndex; i -= M)
    dist += arr[i] * 2;
  for (int i = 0; i < positiveStartIndex; i += M)
    dist += ABS(arr[i]) * 2;

  int max = 0;
  for (int i = 0; i < N; i++) {
    max = ABS(arr[i]) > max ? ABS(arr[i]) : max;
  }
  dist -= max;
  printf("%d", dist);
}