백준 1461번: 도서관 (C++)

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

1461번: 도서관

---

Solved By: Greedy, Sort

 

우선 0을 기준으로 양수와 음수를 넘나드는 것은 비효율적이기 때문에 0을 시작점으로 두고 음수에 대해서만 생각해봤습니다.

테스트 케이스 1에서 음수 값들을 모두 절댓값 크기 순대로 정렬하면 {39, 37, 29, 28, 6}과 같은 순으로 나옵니다.

M = 2이기 때문에 {39, 37}, {29, 28}, {6}으로 가서 39 * 2 + 29 * 2 + 6 = 142라는 결과를 가져올 것인지

{6}, {29, 28}, {39, 37} 순으로 가서 6 * 2 + 29 * 2 + 39 = 109라는 결과를 가져올 것인지 나누어볼 수 있었습니다.

 

즉, 멀리 있는 것부터 갔다 올 것이냐 or 가까이 있는 것부터 갔다 올 것이냐를 선택하면 됩니다. (그리디)

당연하게도 어떤 한 책을 갔다 두는 데에도 거리를 2번 걸으니 가까운 곳 2번 걷는 것이 최소 선택지입니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, M;
vector<int> pa, ma;

int getSum(vector<int>& v){
    if(v.empty()) return 0;
    
    int ret = 0;
    for(int i = 0; i < v.size(); i += M){
        ret += v[i] * 2;
    }
    
    return ret;
}

bool cmp(int a, int b){
    return a > b;
}

int main(){
    cin >> N >> M;
    for(int i = 0; i < N; i++){
        int b; cin >> b;
        if(b > 0) pa.push_back(b);
        else ma.push_back(-b);
    }
    
    sort(pa.begin(), pa.end(), cmp);
    sort(ma.begin(), ma.end(), cmp);
    
    int res_p = getSum(pa);
    int res_m = getSum(ma);
    int m_value;
    
    if(pa.empty()) m_value = ma[0];
    else if(ma.empty()) m_value = pa[0];
    else m_value = max(ma[0], pa[0]);
    
    cout << res_p + res_m - m_value;
    return 0;
}