[ 백준 ] 1461 / 도서관

金弘均·2021년 9월 15일
0

Baekjoon Online Judge

목록 보기
121/228
post-thumbnail

# Appreciation

/*
 * Problem :: 1461 / 도서관
 *
 * Kind :: Greedy
 *
 * Insight
 * - 가능한 경우를 다 따져보기에는 너무 많은 것 같은데...
 *   일단 예제 부터 이해하자
 *   + 끙끙댄 결과,
 *     -39 -37 -29 -28 -6 2 11
 *     (2, 11)      / 22
 *     (-6)         / 12
 *     (-29, -28)   / 58
 *     (-39, -37)   / 39
 *     이렇게 해야지 131 걸음으로 모두 책을 제자리에 둘 수 있다
 *     # 순서 상관 없이 저 조합으로 책을 두기만 하면 된다
 *       저 조합만 뽑아낼 수 있나...?
 *       Greedy 로 풀면 되나...?
 *       -> 원래 위치가 음수인 책과 양수인 책을 같이 조합하는 건 비효율적이다
 *          (2, -6) 은 (2) 와 (-6) 을 하는 거랑 걸음 수에서 다를 바가 없다!
 *          적어도 같은 조합에 있는 책들이 같은 부호여야지만 걸음 수를 절약할 수 있다
 *
 * - (-10, -1) => 필요한 걸음 수 20
 *   (-10, -9) => 필요한 걸음 수 20
 *   그럼 무조건 제일 멀리 있는 같은 부호의 책들부터 M 개씩 옮겨야 겠다
 *   # 근데 마지막에 돌아올 필요 없으니 제일 멀리 있는 위치의 책을 걸음 수에서 빼주자
 *
 * Point
 * - 원래 위치가 음수인 책들을 둘 때 원래 위치의 절댓값으로 걸음 수 계산을 해야하는 것만 주의하자
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

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

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N, M;
    cin >> N >> M;
    int P[N];
    for (int i=0; i<N; i++) {
        cin >> P[i];
    }

    // Process
    vector<int> pos, neg; /* 원래 위치가 양수인 책들과 음수인 책들 구분 */
    for (int p : P) {
        (p > 0) ? pos.push_back(p) : neg.push_back(p);
    }
    /* 각각 절댓값이 큰 순서(멀리 떨어진 순서)대로 정렬 */
    sort(pos.begin(), pos.end(), greater<>());
    sort(neg.begin(), neg.end());

    int ans = 0;
    for (int i=0; i<pos.size(); i+=M) {
        ans += 2*pos[i]; /* 갔다가 돌아와야 하므로 필요한 걸음 수는 2배 */
    }
    for (int i=0; i<neg.size(); i+=M) {
        ans += 2*abs(neg[i]); /* 갔다가 돌아와야 하므로 필요한 걸음 수는 2배 */
    }

    /* 책을 다 정렬한 후 돌아올 필요가 없음,
     * 그러므로 가장 멀리 떨어진 책의 원래 위치의 절댓값 만큼 걸음에서 빼줌 */
    ans -= max(abs(*min_element(P, P+N)), *max_element(P, P+N));

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글