C++ 백준 1461번 : 도서관

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

1461번: 도서관

문제

세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔둘 때 드는 최소 걸음 수를 계산하는 프로그램을 작성하시오. 세준이는 한 걸음에 좌표 1칸씩 가며, 책의 원래 위치는 정수 좌표이다. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다. 그리고 세준이는 한 번에 최대 M권의 책을 들 수 있다.

입력

첫째 줄에 책의 개수 N과, 세준이가 한 번에 들 수 있는 책의 개수 M이 주어진다. 둘째 줄에는 책의 위치가 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 책의 위치는 0이 아니며, 절댓값은 10,000보다 작거나 같은 정수이다.

출력

첫째 줄에 정답을 출력한다.

---

풀이

 먼저 입력받은 위치를 0보다 큰 것과 작은 것으로 나누어 벡터에 저장하고 정렬해주었다.

 위치 개수가 짝수든 홀수든 맨 먼 곳까지 가야하기 때문에 제일 먼 곳부터 곱하기 2씩 하고 한 번에 들 수 있는 책의 개수만큼 빼주었다. 종료조건은 책의 개수만큼 빼주다 0보다 작아지면 그만두었다. 마이너스벡터와 플러스벡터 모두 위치만큼 더해준 후, 마지막으로 0으로 돌아가지 않아도 되기 때문에 마이너스벡터중에 절댓값이 젤 큰 값과 플러스벡터중에 젤 큰 값중 비교하여 더 큰 값을 위치에서 빼주었다.

 여기에 0보다 큰 숫자만 있을 경우, 0보다 작은 숫자만 있을 경우 예외처리를 해주었다 ~

ex)

7 2
-37 2 -6 -39 -29 11 -28

마이너스 벡터 : -39 -37 -29 -28 -6

플러스 벡터 : 2 11

 

마이너스 벡터에서 절댓값을 취해 39*2 + 29*2 + 6*2 = 148

플러스 벡터는 11 * 2 = 22

총 170 에서 

마이너스 벡터에서 젤 큰 값 39 와 플러스 벡터에서 제일 큰 값 11을 비교해주어 더 큰 값을 빼주면 된다.

정답 : 170-39 = 131

---

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

vector <int> v_plus;
vector <int> v_minus;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int num, carry;
	int ans = 0; // 정답
	cin >> num >> carry;
	// 0보다 작은 것, 큰 것 분류
	for (int i = 0; i < num; i++) {
		int tmp;
		cin >> tmp;
		if (tmp > 0) {
			v_plus.push_back(tmp);
		}
		else {
			v_minus.push_back(tmp);
		}
	}

	// 정렬
	sort(v_plus.begin(), v_plus.end());
	sort(v_minus.begin(), v_minus.end());
	
	if (v_minus.empty()) { // 0보다 큰 숫자만 있을 경우
		for (int i = v_plus.size() - 1; i >= 0; i -= carry) {
			ans += v_plus[i] * 2;
		}
		ans -= v_plus.back();
		cout << ans << endl;
		return 0;
	}
	else if(v_plus.empty()){ // 0보다 작은 숫자만 있을 경우
		for (int i = 0; i <= v_minus.size(); i += carry) {
			ans += abs(v_minus[i]) * 2;
		}
		ans += v_minus.front();
		cout << ans << endl;
		return 0;
	}
	// +벡터와 -벡터 carry만큼 거리 + 또는 - 해서 거리 구한후
	// +벡터와 abs(-벡터) 둘 중 큰 값 하나 빼주기
	// 이유 : 갔다가 다시 0으로 안와도 되니까
	for (int i = v_plus.size() - 1; i >= 0; i -= carry) {
		ans += v_plus[i] * 2;
	}
	for (int i = 0; i <= v_minus.size(); i += carry) {
		ans += abs(v_minus[i]) * 2;
	}

	if (abs(v_minus.front()) <= v_plus.back()) {
		ans -= v_plus.back();
	}
	else {
		ans += v_minus.front();
	}
	cout << ans << endl;
}