[BOJ] 1461번 도서관 (C++)

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

1461번: 도서관

 

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

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

int main() {
	int n, m, p, res = 0;
	vector<int> book_l;
	vector<int> book_r;
	
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		cin >> p;
		if(p < 0) book_l.push_back(p);
		else book_r.push_back(p);
	}
	
	sort(book_l.begin(), book_l.end());
	sort(book_r.begin(), book_r.end(), compare);
	
	for(int i = 0; i < book_l.size(); i += m){
		res += abs(book_l[i]) * 2;
	}
	for(int i = 0; i < book_r.size(); i += m){
		res += book_r[i] * 2;
	}
	
	if(book_l.empty()) res -= book_r[0];
	else if(book_r.empty()) res -= abs(book_l[0]);
	else if(abs(book_l[0]) > book_r[0]) res -= abs(book_l[0]);
	else res -= book_r[0];
	
	cout << res << endl;
	return 0;
}

 

 

문제의 예시에서 M이 2이고, 음수 위치에 있는 책들이 [-39, -37, -29, -28, -6]이라면 

(-6, -28), (-29, -37), (-39) 순서로 가져가는 경우에 이동 거리는 (28 + 37 + 39) * 2이고,

(-6), (-28, -29), (-37, -39) 순서로 가져가는 경우에 이동 거리는 (6 + 29 + 39) * 2로

거리가 멀리 있는 책부터 가져다 놓는 것이 이동 거리가 짧다.

따라서 음의 위치에 있는 책을 담는 벡터와 양의 위치에 있는 책을 담는 벡터를 정의하고, 두 벡터를 절댓값에 대해 내림차순으로 정렬한다.

 

각각의 벡터에서 절댓값이 가장 큰 수부터 m개씩 끊고, 해당 원소 * 2 하여 최소 이동 거리를 구한다.

 

이 때 주의할 점은 모든 책을 가져다 놨으면 원래 0 위치로 돌아올 필요가 없으므로, 마지막 위치를 빼야한다.

이 값이 가장 커야 최소 이동 거리가 되므로, 절댓값이 가장 큰 책의 위치를 뺀다.