[BOJ] 1461 도서관

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

1461번: 도서관

책을 옮길 때 책이 0에 위치하므로, 양수와 음수 중 한 부분을 끝내고 다음에 다른 부분을 끝내는 것이 효율적이기 때문에 책의 위치를 양수부분과 음수 부분으로 나누어서 저장하였다.

 

양수 부분이든 음수 부분이든 그 절댓값(거리)이 가장 큰 곳을 방문할 때가 M권의 책 중 가장 마지막 책을 옮길 때여야지 이동거리를 최소화 할 수 있다. 따라서 처음에는 M권의 책을 모두 들고가는 것이 아니라 해당 부분(양수,음수)의 크기를 M으로 나눈 나머지 만큼만 책을 가져가게 처리 해주어야 한다.

 

또, 마지막 부분은 다시 0으로 돌아갈 필요가 없으므로 양수 부분과 음수 부분 중 절댓값이 가장 큰 값을 빼줘야 한다.

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

vector<int> v_plus;
vector<int> v_minus;
int N,M;

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int x;
    cin>>N>>M;
    
    for(int i=0;i<N;i++){
        cin>>x;5
        if(x>0) v_plus.push_back(x);
        else v_minus.push_back(x);
    }
    
    sort(v_plus.begin(),v_plus.end());
    sort(v_minus.begin(),v_minus.end(),greater<int>());
    
    int p_rest=v_plus.size()%M,m_rest=v_minus.size()%M;
    int p_sum=0,m_sum=0;
    
    if(p_rest!=0)
        p_sum+=(2*v_plus[p_rest-1]);
    
    if(m_rest!=0)
        m_sum+=abs(2*v_minus[m_rest-1]);
    
    
    int cnt=0;
    for(int i=p_rest;i<v_plus.size();i++){
        if(++cnt%M==0){
            cnt=0;
            p_sum+=(2*v_plus[i]);
        }
    }
    
    cnt=0;
    for(int i=m_rest;i<v_minus.size();i++){
        if(++cnt%M==0){
            cnt=0;
            m_sum+=abs(2*v_minus[i]);
        }
    }
    
    int ans=(p_sum+m_sum);
    int m_max=0,p_max=0;
    
    if(v_plus.size()>0) p_max=v_plus[v_plus.size()-1];
    if(v_minus.size()>0) m_max=abs(v_minus[v_minus.size()-1]);
    
    ans-=max(p_max,m_max);
    cout<<ans;
    
    return 0;
}