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

풀이

최소 걸음 수를 구하는 법은 다음과 같다.
(예제 입력 1)을 예시로 들어보자.
7권의 책이 있고, 한 번에 2권의 책만 나를 수 있고 입력값은 -37 2 -6 -39 -29 11 -28 이다.
이 경우의 최소값을 구하기 위해서는 제일 멀리 떨어진 책은 마지막에 가져다 놔야 한다.
그러는 이유는 나머지 경우의 수는 책의 초기 위치가 0이라 가져다 놓은 이후, 다른 책을 가져다 놓기 위해서 다시 0의 위치로 돌아와야 하기에 걸음 수는 이동거리 2 가 된다.
그렇기에 만약 제일 큰 숫자를 마지막으로 가져다 놓게 된다면 이동거리 1 만 해줘도 되기에 최소값을 구할 수 있다.
-37 2 -6 -39 -29 11 -28 을 정렬하게 된다면 -39 -37 -29 -28 -6 2 11 이다.
절대값이 제일 큰 숫자인 -39를 우리는 마지막에 가져다 놓아야 한다.
추가적으로 음수와 양수를 구분하여 이동거리를 최소화 시켜주었다.
한번 이동할 때는 M만큼의 책을 들어야 하기에 큰 숫자부터 M개씩 끊어주면 된다.

 

• 이동거리 : 0 책 : -39 -37 -29 -28 -6 2 11

양수부터 해결하자. M이 2이고 2개씩 끊으면 11이 이동해야 할 거리다. 이후 0으로 돌아와야 하므로 이동거리는 11*2다.

• 이동거리 : 22 책 : -39 -37 -29 -28 -6

이후 -39 -37은 제일 큰 숫자이니 한번만 더해주면

• 이동거리 : 51 책 : -29 -28 -6

다음으로 29를 계산해주면 29 * 2이므로

• 이동거리 : 109 책 : -6

마지막으로 -6까지 계산해주면

• 이동거리 : 131 이란 결과가 나오게 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void init() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
}

int main() {
	init();

	int N, M;
	vector<int> plusV, minusV;	// 입력값을 양수와 음수로 구분하기 위해 두 개의 벡터를 선언해주었다.
	int ans = 0;

	cin >> N >> M;


	for (int i = 0; i < N; i++) {
		int in;
		cin >> in;

		if (in > 0) {	// 만약 입력값이 양수이면 plusV에 저장한다.
			plusV.push_back(in);
		}
		else {	// 그렇지 않으면 minusV에 저장된다.
			minusV.push_back(-in);
		}
	}

	// 만약 두 벡터의 크기가 M의 배수가 아니라면 그만큼 0을 추가해준다.
	while (true) {
		if (plusV.size() % M != 0) {
			plusV.push_back(0);
		}
		else if (minusV.size() % M != 0) {
			minusV.push_back(0);
		}
		else break;
	}

	while (true) {
		if (plusV.size() == 0) {
			for (int i = 0; i < M; i++) {
				plusV.push_back(0);
			}
		}
		else if (minusV.size() == 0) {
			for (int i = 0; i < M; i++) {
				minusV.push_back(0);
			}
		}
		else break;
	}

	sort(plusV.begin(), plusV.end());
	sort(minusV.begin(), minusV.end());

	// 만약 플러스의 제일 큰 값이 마이너스의 제일 큰 값보다 크다면.
	// 즉 플러스의 값을 편도로 처리해야 한다면
	if (abs(plusV.back() > minusV.back())) {
		ans += plusV.back();
		for (int i = 0; i < M; i++) {
			plusV.pop_back();
		}
	}
	else if (abs(plusV.back() < minusV.back())) {
		ans += minusV.back();
		for (int i = 0; i < M; i++) {
			minusV.pop_back();
		}
	}
	else {
		ans += minusV.back();
		for (int i = 0; i < M; i++) {
			minusV.pop_back();
		}
	}

	for (int i = 0; i < plusV.size() / M; i++) {
		ans += plusV.back() * 2;
		for (int j = 0; j < M; j++) {
			plusV.pop_back();
		}
	}

	while (!plusV.empty()) {
		ans += plusV.back() * 2;
		for (int k = 0; k < M; k++) {
			plusV.pop_back();
		}
	}

	while (!minusV.empty()) {
		ans += minusV.back() * 2;
		for (int k = 0; k < M; k++) {
			minusV.pop_back();
		}
	}

	cout << ans;

	return 0;
}

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