(백준) 1477번 - 휴게소 세우기

문제

풀이

처음에는 다음과 같은 방법으로 휴게소를 설치하였다.

1. 휴게소 간 거리 중 가장 긴 거리를 찾는다.
2. 중간에 휴게소를 설치한다.
3. 위 과정을 $M$번 반복한다.

이러한 그리디 접근 방식은 최적의 해를 보장하지 않는다. $M = 2,\ L=100$이고, 휴게소가 0과 100 지점에 있다고 할 때, 위 방법의 최대 길이는 50이다. 그러나 최적해는 거리 100을 3등분하는 경우이고, 최대 길이는 34이다.

---

매개변수 탐색으로 휴게소 간 최대 길이를 구한다. left를 1, right를 l로 설정하고, mid를 휴게소 간 최대 길이로 한다. mid일 때 휴게소를 배치하고, $M$과 비교하여 left 또는 right를 조정한다.

코드

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

using namespace std;

vector<int> v;

// 휴게소 간 최대 거리를 x로 했을 때, 설치 가능한 휴게소의 수를 리턴
int chk(int x) {
	int cnt = 0;
	for (int i = 0; i < v.size() - 1; i++) {
		int gap = v[i + 1] - v[i];

		if (gap % x == 0) {
			cnt += gap / x - 1;
		}
		else {
			cnt += gap / x;
		}
	}

	return cnt;
}

int main() {
	int n, m, l;
	cin >> n >> m >> l;

	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		v.push_back(x);
	}
	v.push_back(0);
	v.push_back(l);

	sort(v.begin(), v.end());

	int left = 1;
	int right = l;
	int mid;
	while (left <= right) {
		mid = (left + right) / 2; // mid: 휴게소 간 최대 거리

		int cnt = chk(mid);

		if (cnt <= m) {
			right = mid - 1;
		}
		else {
			left = mid + 1;
		}
	}

	cout << left;
}

시간복잡도

초기 벡터 정렬에서 $O(NlogN)$, 매개변수 탐색은 루프에서 $O(logL)$, chk 함수에서 벡터를 순회하므로 $O(N)$이므로, $O(NlogL)$이다.

따라서 최종 시간복잡도는 $O(NlogN + NlogL)$이다.

공간복잡도

휴게소는 최대 $N+2$개 가능하므로(0은 제외) 공간복잡도는 $O(N)$이다.