백준 BOJ 1461 - 도서관

깔끔하게 풀어서 마음에 드는 문제.

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

1461번: 도서관

 

음수 위치의 책을 집고 양수 위치의 책을 또 집는것은 이동거리의 낭비가 되기 때문에,

음수 위치에 있는 책들끼리 묶어서 옮기고

양수 위치에 있는 책들끼리 묶어서 옮기려는 생각을 해야 한다.

$M$개씩 묶어서 옮기는 과정에서,

이동거리는 묶인 것들 중 가장 절댓값이 큰 숫자의 두배(왕복) 이 된다.

 

제일 마지막에는 다시 0으로 돌아올 필요가 없고,

왕복하느라 이미 제일 마지막의 수는 두번 더해져있을 것이기 때문에

절댓값이 가장 큰 수 하나를 빼주면 된다.

 

빼는 과정에서 양수 좌표만 있거나, 음수 좌표만 있는 경우

OutOfBounds 에러가 발생할 수 있다.

케이스 잘 나눠서 처리해줘야 한다.

 

#include <bits/stdc++.h>
using namespace std;

vector<int> p;
vector<int> m;

int main(){
	int N,M,k;
	cin >> N >> M;
	for(int i=0; i<N; i++){
		cin >> k;
		if(k > 0) p.push_back(k);
		else      m.push_back(k);
	}
	
	sort(p.begin(), p.end(), greater<int>());
	sort(m.begin(), m.end());
	
	int ans = 0;
	for(int i=0; i<p.size(); i+=M) ans += (p[i] *  2);
	for(int i=0; i<m.size(); i+=M) ans += (m[i] * -2);
	
	int sub = 0;
	if(p.size() != 0) sub = p[0];
	if(m.size() != 0) sub = max(sub, -m[0]);
	
	cout << ans - sub;
	return 0;
}