[백준 / C++] 1461번: 도서관 (그리디 알고리즘)

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

1461번: 도서관

 

난이도: solved.ac 골드 4

 

알고리즘 분류

정렬, 그리디 알고리즘

 

접근 방법

우선 문제 조건 중 책을 모두 제자리에 놔둔 후, 즉 맨 마지막으로 옮길 때는 다시 0으로 돌아가지 않아도 된다는 조건을 빼고 생각해보자.

 

걸음의 수를 최소화하기 위해서는 양수에서 절댓값이 큰 것끼리 M개씩 묶어 옮기고, 음수에 절대값이 큰 것끼리 M개씩 묶어 옮기면 된다.

 

예제 입력 1에서는

양수: (2, 11)

음수: (-39, -37), (-29, -28), (-6)

이렇게 옮기는 것이다.

 

그리고 여기서 절댓값이 가장 큰 책이 들어가 있는 쌍을 맨 마지막으로 옮기면 된다.

 

위에서 만든 쌍은 이미 걸음을 최소화하기 위한 최적의 쌍들이고 모두 두 번 더해지는데, 여기서 최소화를 유지하면서 한 번만 더해도 되는 것을 고르자면 절댓값이 가장 큰 것을 골라야 하기 때문이다.

 

코드

#include <bits/stdc++.h>
using namespace std;
// 백준 1461번: 도서관 (골드 4)
vector<int> neg, pos;	// 음수, 양수

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int N, M, num, i, ans = 0;
	cin >> N >> M;
	while (N--) {
		cin >> num;
		if (num > 0)
			pos.push_back(num);
		else {
			num = (-num);
			neg.push_back(num);
		}
	}
	int nneg = neg.size();
	int npos = pos.size();
	sort(neg.begin(), neg.end());
	sort(pos.begin(), pos.end());
	for (i = nneg - 1; i >= 0; i -= M)
		ans += neg[i] * 2;
	for (i = npos - 1; i >= 0; i -= M)
		ans += pos[i] * 2;
	if (nneg > 0 && npos > 0) {
		if (neg[nneg - 1] > pos[npos - 1])
			ans -= neg[nneg - 1];
		else
			ans -= pos[npos - 1];
	}
	else if (nneg > 0) {
		ans -= neg[nneg - 1];
	}
	else
		ans -= pos[npos - 1];
	cout << ans;
}

 

성능

코드 제출 결과