# 1461. 도서관

관련 알고리즘 : 그리디, 정렬

 

문제 링크 : https://www.acmicpc.net/problem/1461

1461번: 도서관

---

해결 과정

 

문제에서 제공한 예시를 토대로 생각해보면,

책의 위치들을

{-39, -37, -29, -28, -6, 2, 11} 순으로 오름차순 정리할 수 있다.

어차피 모든 책들을 다 제자리에 갖다 놓아야 하고, 마지막 책은 놓고 나서 다시 0으로 되돌아올 필요가 없기 때문에

 가장 먼 거리에 있는 책을 제일 마지막에 놓는 것이 이동거리를 줄일 수 있다.

 

예시에서 세준이가 한번에 들 수 있는 책은 2권이므로 이를 토대로 2권씩 각 책들을 거리순대로 나눠보면,

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

이 때, 양수와 음수를 구분하여 나누는 것이 이동거리를 최소화 할 수 있다.

절댓값으로 놓고 봤을때 가장 먼 거리에 있는 책이 있는 묶음이 {-39, -37} 이므로

-39 위치에 있는 책을 가장 마지막에 갖다 놓는 길에 -37 위치의 책을 갖다 놓으면

이동거리 39만으로 두개의 책을 다 제자리에 놓을 수 있다.

즉,

(최단 이동거리) = (각 묶음에서 절댓값이 더 큰 묶음)x2 + (총 책들 중 절댓값이 가장 큰 위치에 있는 책까지의 거리)

(최단 이동거리) = (29 + 6 + 11)x2 + 39 = 131

 

---

C++ 코드

// 백준 1461. 도서관

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;

int n, m; // 책 개수 n, 한 번에 들 수 있는 책 개수 m
int book[10001]; // 책 위치
int cnt, res = 0; 
int ans = 0;

void input()
{
    cin >> n >> m;
    for(int i=0; i<n; i++)
    {
        cin >> book[i];
        if(book[i]<0) // 책의 위치가 음수일 때
        {
            cnt+=1;
        }
    }
}

int replace()
{
    sort(book, book+n); // 책 위치순 정렬

    for(int i=0; i<cnt; i+=m) // 음수 위치 책들 m개 단위로 묶기
    {
        res += abs(book[i]*2); // 왕복값 2배
    }
    for(int i= n-1; i>=cnt; i-=m) // 양수 위치 책을 m개 단위로 묶기
    {
        res += (book[i]*2); // 왕복값 2배
    }

    res -= max(abs(book[0]), abs(book[n-1])); // 절댓값 제일 큰 책 위치 편도값 빼기
    return res;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    input();
    ans = replace();

    cout << ans;
}