[백준] 1461번 도서관 (C++)

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

 

문제

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

입력

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

 

 

예제 입력 1 복사

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

예제 출력 1 복사

131

예제 입력 2 복사

8 3
-18 -9 -4 50 22 -26 40 -45

예제 출력 2 복사

158

 

최소한으로 이동해서 모든 책을 원위치로 되돌려 놓아햐하는 문제로 최적 문제를 보면 생각나야하는 것이

 

BFS, 다익스트라, 그리디, DP등이 떠올라야한다.

 

이 문제는 책을 두고나서 다시 0 위치로 돌아와야하는 조건이 있기 때문에 BFS, 다익스트라는 제외한다.

 

내가 사서라고 시뮬레이션해보자, 당연히 가장 가까운 곳부터 다녀오고 마지막 책을 꽂은 후 퇴근하는게 최적이라는 것을 본능에 따라 알 수 있다. 그렇기 때문에 정렬을 해본다. 

 

예제를 진행해보면

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

 

이며 두권을 최대로 들고다닐 수 있으므로

 

(-39 -37) (-29 -28) (-6 2) (11)

 

이렇게 묶고 가장 작은 순서로 진행하면? 답이아니다!

 

왜냐하면 -, + 로 방향이 나뉘어져 있기 때문이다. +끼리, -끼리 진행해야한다.

 

이렇게 묶으면 최적의 상태가 된다. 이 묶은 것들을 어떤 순서로 진행해야할까

 

순서로 진행하면 될까? 아니다. 마지막 위치로 간 후에는 다시 돌아오지 않아도 되기 때문에 +, - 중 절댓값이 가장 큰 곳을 나중에 진행해야한다. 즉

(2 11)  (-6)(-29 -28)(-39 -37)

 

순서로 진행해야한다. 그리고 M으로 나누어 떨어지지 않는다면 가장 작은 것들을 M보다 작은 수로 묶어서 먼저 진행해야한다.

 

이것을 모두 정리하면 다음과같은 탐욕 조건이 나온다.

 

/**

* 가장 먼 곳은 마지막에 간다.

* 가장 가까운 곳은 처음에 간다.

* M으로 책의 수가 나누어 떨어지지 않으면 가장 가까운 책들을 나머지의 수 만큼 묶는다.

* +, - 위치의 책을 함께 들지 않는다.

* +, - 중 마지막 절댓값이 더 작은 곳을 먼저 한다.

*/

 

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

using namespace std;

int N, M;

int cal(vector<int> books){
    if(books.size() == 0) return 0;

    if(books.size() < M){
        return 2 * books[books.size() - 1];
    }

    for(int i = 0; i < books.size() % M; i++){
        books.push_back(0);
    }

    sort(books.begin(), books.end());

    int idx = M - 1;

    int res = 0;

    while(idx < books.size()){
        res += books[idx] * 2;

        idx += M;
    }

    return res;
}

int main(){
    cin >> N >> M;

    vector<int> plus;
    vector<int> minus;
    for(int i = 0; i < N; i++){
        int tmp;
        cin >> tmp; 

        if(tmp < 0){
            minus.push_back(abs(tmp));
        }else{
            plus.push_back(tmp);
        }
    }

    sort(plus.begin(), plus.end());
    sort(minus.begin(), minus.end());

    int answer = cal(plus) + cal(minus);

    if(plus.size() > 0 && minus.size() > 0){

    if(plus[plus.size() - 1] > minus[minus.size() - 1]){
        answer -= plus[plus.size() - 1];
    }else{
        answer -= minus[minus.size() - 1];
    }
    }

    if(plus.size() == 0) answer -= minus[minus.size() - 1];
    if(minus.size() == 0) answer -= plus[plus.size() - 1];

    cout << answer << '\n';
}