[백준 BOJ/C++] 1461 도서관

1461번: 도서관

전형적인 그리디 알고리즘 문제이며 단순하다면 단순한 편이지만 처음 접했을 때 문제를 정확히 이해하지 못했었다.
쉬운 편의 문제라고 할 수 있겠지만 문제 설명이 자세하고 친절하지는 않은 편이라 헤맬 수 있는 문제다.

 

 

1차원 수평선 위 0에서 시작해 음수와 양수 구간을 효율적으로 이동시키도록 하는 문제다.
한번에 옮길 수 있는 책 수의 제한이 있어서 다시 시작점인 0으로 돌아오는 것을 고려해야 하는데 마지막에는 돌아오지 않아도 된다.
최소 몇 회 만에 옮길 수 있는지 찾아야 한다.

 

 

---

 

문제의 포인트

1. 한번에 이동시킬 수 있는 책의 수
2. 돌아오는 구간과 마지막 구간 선택
3. 음수 구간과 양수 구간의 표현

 

 

한번에 이동시킬 수 있는 책의 수

수평선에서 좌,우로의 이동을 이용하는 문제이므로 우선 그림과 같이 실제 수평선에 그려보면 이해가 쉽다.
예제에서는 한번에 2권의 책을 옮길 수 있으므로 가장 먼곳까지 간다면 그 바로 앞 지점에 두어야 하는 책 1권까지 함께 처리할 수 있다.

 

 

가장 거리가 먼 -39 위치를 마지막에 선택한다면

 

 

그림에서 파란 동그라미로 표시한 지점이 2권씩 옮길 때 반드시 도달해야하는 지점이 된다.
회색 점은 파란점까지 가면서 함께 처리하는 곳으로 거리를 따로 추가해주지 않아도 된다.

 

 

이와 같이 한번에 이동시킬 수 있는 책의 수 M은 각 점을 순서대로 정렬시켰다고 할 때 참조할 index 사이 offset이 된다.
즉, M 만큼 간격을 두고 data를 취해서 더하면 쉽게 이 조건을 구현할 수 있다.

 

 

돌아오는 구간과 마지막 구간 선택

아직 정리해야하는 책이 남아있는 경우 다시 시작점인 0으로 돌아와야 한다.
따라서 반드시 들러야 하는 파란점에 해당하는 거리는 2를 곱해 왕복 거리로 더해줘야 한다.

 

 

하지만 마지막 M권의 책만 남은 경우 시작점으로 돌아올 필요가 없으므로 전체 이동 거리의 최소화를 위해서는 가장 먼 거리의 책을 맨 마지막에 정리하는 것이 유리하다.
좌표는 음수 지점도 포함하고 있으므로 절대값이 가장 큰, 거리가 가장 긴 지점에 대해서는 '* 2'를 하지 않거나 마지막에 다시 빼주는 형태로 쉽게 구현해볼 수 있다.

 

 

음수 구간과 양수 구간의 표현

답을 찾는데 필요한 data는 거리인데 좌표는 음수, 양수를 포함한다.
즉, 좌표가 음수인 지점의 경우 절대값으로 이용해야 한다.

그리고 시작점은 항상 0이기 때문에 음수 좌표 지점과 양수 좌표 지점은 이동 방향이 반대가 된다.

 

그림에서 -6 지점에 책을 두러갈 때에는 1권만 가져가는 것으로 처리하듯 한번에 옮길 수 있는 책의 수 M을 고려할 때 방향을 고려해야 하므로 음수와 양수 좌표는 별개로 처리해주는 것이 좋다.

 

 

만약 하나의 배열에 모든 좌표를 넣어서 처리한다면 시작점인 0을 함께 넣고 전체 정렬을 시켜서 0이 위치한 배열의 index를 이용해 좌, 우로 자료 구조를 활용해도 좋을것 같다.
더 쉬운 방법으로는 음수, 양수 좌표용 배열을 각각 만들어 처리하면 보다 구현이 쉽고 간단해진다.

 

 

---

 

전체 Code

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

using namespace std;

int N, M;
vector<int> neg;
vector<int> pos;

int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);

	int i, temp, sum = 0;

	cin >> N >> M;

	for (i = 0; i < N; i++) {
		cin >> temp;
		if (temp > 0) {
			pos.push_back(temp);
		}
		else {
			neg.push_back(-temp);
		}
	}

	sort(neg.begin(), neg.end(), greater<int>());
	sort(pos.begin(), pos.end(), greater<int>());

	for (i = 0; i < neg.size(); i+= M) {
		sum += neg[i] * 2;
	}
	for (i = 0; i < pos.size(); i+=M) {
		sum += pos[i] * 2;
	}

	if (neg.empty()) {
		sum -= pos[0];
	}
	else if (pos.empty()) {
		sum -= neg[0];
	}
	else {
		sum -= max(neg[0], pos[0]);
	}

	cout << sum << "\n";
    
	return 0;
}