BOJ 1461 : 도서관

• 문제 링크 : boj.kr/1461
• 난이도 : G4
• 태그 : 그리디, 정렬

1461번: 도서관

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

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

    int n, m;
    cin >> n >> m;
    vector<int> neg, pos;
    for(int i = 0; i < n; i++) {
        int input;
        cin >> input;
        if(input < 0) neg.push_back(-input);
        else pos.push_back(input);
    }
    sort(all(neg), greater<int>());
    sort(all(pos), greater<int>());

    int ans = 0;
    int M = 0;
    for(int i = 0; i < neg.size(); i += m) {
        ans += neg[i] * 2;
        M = max(M, neg[i]);
    }
    for(int i = 0; i < pos.size(); i += m) {
        ans += pos[i] * 2;
        M = max(M, pos[i]);
    }
    cout << ans - M;

    return 0;
}

---

풀이

음수 좌표의 책과 양수 좌표의 책을 동시에 챙겨서 가져다 놓는 것은, 따로 챙겨서 가져다 놓는 것과 다르지 않다.

따라서 음수 좌표의 책과 양수 좌표의 책을 따로 볼 것이다.

 

모든 책을 가져다 놓기 위해서는 각각의 책의 좌표에 한 번씩은 도달해야 한다. 또한 들고 있는 책을 모두 가져다 놓고 나면 새로운 책을 가져다 놓기 위해 처음의 위치로 돌아와야 한다. 따라서 한 번에 옮기는 책 중 가장 먼 좌표의 절댓값 * 2 만큼 움직여야 한다.

이때 마지막에는 처음 위치로 돌아오지 않아도 되지만, 우선은 처음 위치로 돌아온다고 생각하고 문제를 풀어보자.

 

이 경우 먼 순서의 책부터 m개씩 책을 챙겨서 놓고 처음위치로 돌아오는 것이 최적이다.

우선 책을 한 권씩만 챙겨서 놓고 온다고 해보자. 그렇다면 이동해야 하는 거리는 모든 책의 좌표의 절댓값의 합 * 2이다.

이때 어떤 책을 놓으면서 다른 책을 함께 챙긴다는 것은 가장 먼 책을 제외한 다른 책의 좌표의 절댓값만큼 이동해야 하는 거리에서 줄어든다는 것과 같다. 따라서 한 번에 최대한 많은 값을 줄여야 하므로 먼 순서부터 책을 챙기는 것이 최적임을 알 수 있다.

 

모든 책을 놓고 처음 위치로 돌아온 상태라고 생각해 보자. 지금까지의 이동 중에 한 번 처음 위치로 돌아오지 않는다면 해답을 구할 수 있다. 가장 멀리 이동했던 경우에 처음 위치로 돌아오지 않는 것이 최적임이 당연하다.