문제

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

입력

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

출력

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

접근 과정

멀리 있는 책을 가져다 두면서 그보다 가까운 위치의 책도 갔다둘 수 있으므로 최소한의 움직임으로 책을 놔두기 위해선 가장 끝부분에서 부터 M권의 책을 한 번에 옮기는게 효율적이다. 남은 책 중 가장 긴 거리의 왕복만큼 더하고 큰 순서대로 M권씩 제거하는 것을 반복한다. 이 과정을 getTotalStep() 함수로 구현하였다.
단, 기준이 되는 위치가 0이기 떄문에 양수 위치에 있는 책과 음수 위치에 있는 책의 거리를 따로 처리를 해주어야 한다. 따라서 입력받은 값을 positive와 negative vector로 나누어 처리하였다.
또한 맨 마지막 책을 두고 다시 0 좌표로 돌아오지 않아도 된다는 조건이 있다. 이 조건을 해석하면 걸음 수가 최소가 되기 위해서는 0으로 부터 가장 멀리 떨어진 위치 까지 이동한 뒤에는 다시 돌아오지 않아야 한다. getTotalStep() 함수는 이미 왕복 거리를 기준으로 계산하였으므로 결과 값에서 가장 멀리 떨어진 거리만큼 빼주었다.

소스 코드

#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;

int getTotalStep(vector<int>& vec, int m) {
    int ret = 0;
    while (!vec.empty()) {
        ret += vec.back() * 2;
        for (int i = 0; !vec.empty() && i < m; ++i) {
            vec.pop_back();
        }
    }
    return ret;
}

int main() {
    vector<int> negative;
    vector<int> positive;
    int N, M;
    int result = 0;

    cin >> N >> M;
    for (int i = 0; i < N; ++i) {
        int num;
        cin >> num;
        if (num > 0) positive.push_back(num);
        else negative.push_back(num * -1);
    }

    sort(negative.begin(), negative.end());
    sort(positive.begin(), positive.end());

    int ml = negative.empty() ? 0 : negative.back();
    int mr = positive.empty() ? 0 : positive.back();

    result += getTotalStep(negative, M);
    result += getTotalStep(positive, M);

    cout << result - max(ml, mr) << endl;
    return 0;
}