[알고리즘] 혼자 못 푼 문제 정리 - 도서관

BOJ 1461 도서관

난이도 : (백준 난이도 기준) 골4

사용 알고리즘 or 자료 구조 : 그리디 알고리즘, 정렬

 

처음 생각한 풀이

1) 현재 위치에서부터 가장 가까운 곳을 찾아 해당 위치를 방문하며, 가지고 있는 책이 0개가 되면 0으로 가는 방식으로 풀었다.(그랬더니 터무니 없이 큰 숫자들이 나왔다.)

 

2) 반대로 절댓값이 큰 곳부터 가는 것으로 풀었더니 역시 답이 제대로 나오지 않았다.

구글링 이후 풀이

1. 먼저 위치가 양수인 책과 음수인 책을 따로 저장해준다.

 

2. 그 후, 양 쪽에서 절대값이 가장 큰 순으로 책을 M개 씩 묶는다.

 

3. 가장 큰 값만 방문하면 나머지는 0으로 돌아오는 길이나 가는 길에 방문하게 되므로 이동 거리는 가장 큰 값의 2배가 된다.

 

4. 마지막으로 양수나 음수 중, 가장 큰 값을 뺀다.

 

ex) 예제 입력 1을 통해 방법을 알아보자

예제 입력 1
7 2
-37 2 -6 -39 -29 11 -28

 

양수 칸 : [2, 11]

음수 칸 : [6, 28, 29, 37, 39] (정렬을 위해 절대값을 취해 저장)

 

절대값이 큰 것부터 2개씩 그룹을 만듦

양수 칸 : [(2, 11)]

음수 칸 : [(-39, -37), (-29, -28), (-6)] 

 

각 그룹의 절대값이 큰 곳만 왕복 방문하므로 모두 더해줌

distance = 11 * 2 + 39 * 2 + 29 * 2 + 6 * 2 = 170

 

가장 절대값이 큰 곳은 마지막에 방문하게 되면 책 정리가 끝나므로 0으로 돌아올 필요가 없음

따라서 해당 값을 빼줌

distance = 170 - 39 = 131

 

 

 

 

 

 

 

 

 

 

 

※ 스 포 주 의 ※

 

 

 

 

 

 

 

 

 

 

 

 

코드

/// BOJ 1461 도서관

#include <iostream>

#include <vector>

#include <algorithm>

#include <cmath>

using namespace std;

int main() {

    int N, M;

    cin >> N >> M;

    vector<int> plus;

    vector<int> minus;

    for(int i = 0; i < N; i++) {

        int book;

        cin >> book;

        if(book > 0) {

            plus.push_back(book);       // 양수에 위치한 책과

        }

        else {

            minus.push_back(-book);     // 음수에 위치한 책을 따로 저장함

        }

    }

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

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

    int answer =0;

    int bigger = 0;

    int pm, mm;

    if(plus.size() && minus.size()) {       // 만약 양 쪽 다 책이 존재한다면

        pm = plus[plus.size() - 1];

        mm = minus[minus.size() - 1];

        if(pm > mm) {

            bigger = 1;                     // 어느 쪽이 더 큰지 표시

        }

        else {

            bigger = -1;

        }

    }

    else if(plus.size()) {                  // 한 쪽에만 존재하면

        pm = plus[plus.size() - 1];         // 어느 쪽이 존재하는지 저장

        bigger = 1;

    }

    else {

        mm = minus[minus.size() - 1];

        bigger = -1;

    }

    for(int i = plus.size() - 1; i >= 0; i -= M) {          // 절대값이 큰 값부터 왕복 시작

        answer += plus[i] * 2;

    }

    for(int i = minus.size() - 1; i >= 0; i -= M) {

        answer += minus[i] * 2;

    }

    if(bigger > 0) {        // 순회 끝난 후 가장 절대값이 큰 값을 한 번 빼줌(마지막은 왕복하지 않고 책 갖다놓고 끝)

        answer -= pm;

    }

    else {

        answer -= mm;

    }

    cout << answer;

    return 0;

}