[ 백준 / 1461 ] 도서관 (C++)

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

 

난이도 : 골드 4 
알고리즘 유형 : 그리디 
풀이 시간 : 51분 

문제 풀이 

문제에서 체크해야 하는 부분은 다음과 같다.

 

1, 정리해야 하는 책의 위치는 0이고, 세준이의 출발 위치도 0이다.

2. 책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다.

 

여기서 주의해야 할 부분은 2번인데, 가장 멀리 위치한 책에 대한 걸음 수는 0으로 돌아오지 않아도 되기 때문에 $*2$를 해주지 않아도 된다.

 

최솟값을 찾으라 했기 때문에 충분히 그리디 알고리즘으로 접근이 가능하다고 생각하였다. 우선 입력값이 $책의 위치 ≤ |10000|$으로 주어지기 때문에 음수와 양수가 존재한다는 것을 알 수 있다. 따라서 `음수 책의 위치`와 `양수 책의 위치`로 나눠주었다. 이후 각 배열을 오름차순 정렬해주었고, 갈 수 있는 모든 거리에 대해서 미리 계산해주었다. 

마지막 걸음 수를 제외한 나머지 걸음 수는 0으로 돌아와야 하기 때문에 두 배 해서 더해주었다. 거리를 계산할 때에는 $손에 들 수 있는 책 중 가장 먼 거리 * 2$로 계산해주었다.

 

그 다음으로, 거리 계산이 안 된 녀석들에 대해서 추가로 계산을 진행해주었다. 이 과정이 왜 필요하나면, 이전에 우리는 `현재 idx + m`으로 인덱스를 계산하였기 때문에, 배열의 크기를 넘어가는 녀석들에 대해서는 계산이 되지 않았을 것이다. 따라서 이 부분을 계산해주었다.

 

마지막으로, 걸음 수가 가장 많이 필요한 부분에 대해서는 한 번 빼주었다. 왜냐하면 이전에 모두 걸음 수의 두 배를 하여 더해주었기 때문이다.

 

코드

/*
도서관

사람들이 마구 놓은 책을 원래 자리에 둬야됨
- 세준이는 현재 0에 위치함
- 마구 놓은 책도 전부 0에 있음
- 책들의 원래 위치가 주어질 때, 책을 모두 제자리에 놔두는 최소 걸음 수를 계산
책을 모두 제자리에 놔둔 후에는 다시 0으로 돌아올 필요는 없다.

풀이:
n <= 50
위치 <= |10000|
정렬 후 그리디 알고리즘으로 해결하면 어떨까 ?
양수 음수 나누기
	- 둘 다 하나만 남았을 땐 어차피 0에 들러야한다
가까운 애들부터 놓기(처음에는 나누어 떨어지지 않는 수만큼 들기)
3개씩 끊어 계산했을 때 마지막 값이 더 작은 쪽부터 가져가기

*/

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#define INIT cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;

int n, m, tmp;

int main() {
	cin >> n >> m;
	vector<int> left_library, right_library;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		if (tmp > 0) right_library.push_back(tmp);
		else left_library.push_back(tmp);
	}

	// 각자 정렬하기
	sort(right_library.begin(), right_library.end());
	sort(left_library.begin(), left_library.end());

	// 가져가기 시작
	int ans = 0;
	int start = 0;
	int end = right_library.size() - 1;
	// 먼저 모든 스텝 확인해보기
	while (start + m < left_library.size()) {
		ans += abs(left_library[start] * 2);
		start += m;
	}
	while (end - m > -1) {
		ans += right_library[end] * 2;
		end -= m;
	}

	// 덜빠진 부분 생각하기
	if (start < left_library.size() && end >= 0)
		ans += (right_library[end] + abs(left_library[start])) * 2;
	else if (start < left_library.size() && end < 0)
		ans += abs(left_library[start]) * 2;
	else
		ans += right_library[end] * 2;

	// 가장 긴 부분은 값을 빼주어야한다(책을 다 정리하면 멈추기 때문)
	if (left_library.empty())
		ans -= right_library.back();
	else if (right_library.empty())
		ans -= abs(left_library[0]);
	else {
		// 둘 다 존재한다면 두 수 비교 후 큰 값 빼주기
		if (abs(left_library[0]) > right_library.back())
			ans -= abs(left_library[0]);
		else
			ans -= right_library.back();
	}

	cout << ans << '\n';

	return 0;
}

배운 점 

최근에 이분탐색 문제를 몇 개 풀어서 그런지 무작정 이분탐색으로만 접근하려 했었다. 그치만 문제를 잘 읽어 해결해나갔다. 또한, 애매한 조건들이 많아 반례를 찾기 쉽지 않았는데 계속해서 반례를 만들어 해결해가는 연습을 진행해야 될 것 같다.