[c++] BOJ 1461번 :: 도서관

도서관

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

문제

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

131

나의 답

생각의 흐름

전체 수 정렬 => 양수와 음수의 절댓값 비교 (없으면 자동으로 정해짐) => 큰 쪽으로 나중에 => 작은 쪽 먼저 큰 수부터 M개씩 끊고, 해당 index 곱하기 2 => 큰 쪽은 절대값이 큰 수부터 M개씩 끊고, 해당 index 곱하기 2 (가장 큰 절댓값은 곱하기 1)

코드

<구현 전 대충 짜기>

sort(arr)
arr1 = 음수 배열 (abs해서 sort)
arr2 = 양수 배열
sum = 0
if(abs(arr1[size-1])<arr2[size-1]): // 음수 먼저
    gothere(0, size);
    flag = 1
    gothere(0, size)

gothere(start,end):
    end-1 ~ start까지 M개씩 끊어서 index 저장 => idx_list
    sum+=idx_list요소*2
    if(flag가 1)
        sum-=idx_list 마지막 요소

<구현>

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N, M;
int booklist[10000];
int positive[10000];
int negative[10000];
int flag = 0;
int sum = 0;

enum {POS,NEG};

void gothere(int start, int end, int kind) {
    int* which;
    if (kind == POS)
        which = positive;
    else
        which = negative;

    vector<int> idx_list;
    int idx = end - 1;
    while (idx >= 0) {
        idx_list.push_back(which[idx]);
        idx -= M;
    }

    for (int i = 0; i < idx_list.size(); i++)
        sum += idx_list[i] * 2;

    if (flag == 1) // 마지막 요소 한 번 빼기
        sum -= idx_list[0];
}

int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        cin >> booklist[i];
    }
    sort(&booklist[0], &booklist[N]);

    // 양수 음수 배열 나누어 담기
    int tmp = 0;
    int n_size = 0;
    while (booklist[tmp] < 0) {
        negative[n_size++] = abs(booklist[tmp++]);
    }
    int p_size = 0;
    while (tmp < N) {
        positive[p_size++] = booklist[tmp++];
    }

    sort(&negative[0], &negative[n_size]);

    if (positive[p_size - 1] < negative[n_size - 1]) { // 절댓값 비교
        gothere(0, p_size, POS); // 작은 거 먼저
        flag = 1;
        gothere(0, n_size, NEG);
    }
    else {
        gothere(0, n_size, NEG); // 작은 거 먼저
        flag = 1;
        gothere(0, p_size, POS);
    }

    cout << sum;

}

테스트 케이스

8 2
-10000 -3 -2 -1 2 100 1000 1001

=> 12206

8 3
-10000 -3 -2 -1 2 100 1000 1001

=> 12008

다른 답

1. 본인은 booklist로 받고 두 배열로 나눴으나 받으면서 바로 양수 음수 조건검사해서 negative, positive 배열로 나눴어도 된다.