[백준] 1508번: 레이스

📌 문제

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

📌 설명

이분 탐색을 통해 가장 가까운 심판 간 거리가 최대가 되는 경우를 찾는다. 백준 2110번: 공유기 설치와 유사한 문제이다. 아래는 공유기 설치 문제에 대한 해답 코드이다.

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

using namespace std;

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

	int n, c;
	cin >> n >> c;

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

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

	int l = 0;
	int r = v[n - 1];
	int ans = 0;

	while (l <= r) {
		int cnt = 1;
		int m = (l + r) / 2;

		int s = v[0];
		for (int i = 1;i < n;i++) {
			if (v[i] - s >= m) {
				cnt++;
				s = v[i];
			}
		}

		if (cnt >= c) {
			ans = max(ans, m);
			l = m + 1;
		}
		else {
			r = m - 1;
		}
	}

	cout << ans;
}

나는 위 코드의 매개변수 탐색 과정에서 아래 구현을 추가하였다.

조건에 맞는 심판들을 배치할 때, $m$ 이하의 심판들만 배치하도록 구현하였다. 여기서 ‘조건’이란, “현재 loop에서 설정한 심판 간 최소 거리를 $\text{mid}$라고 할 때, 이전에 배치한 심판과 현재 심판의 거리가 $\text{mid}$ 이상”이다. 간단히 이야기하면, 공유기 설치 문제에서 ‘조건’에 맞는 모든 공유기들을 설치 후, 설치하려는 공유기의 수보다 많이 설치된 경우 매개변수를 조정하여 다시 탐색하였다. 그러나 나는 배치한 심판의 수를 항상 $m$ 이하로 통제하여 존재하는 심판의 수보다 많이 배치되는 경우를 제외하였다. 이에 대한 반례는 다음과 같다.

20 3 4

0 5 10 15

정답 : 1110

📌 코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
	int n, m, k; // 트랙의 길이, 심판의 수, 지정 공간의 수
	cin >> n >> m >> k;

	vector<int> v(k);
	for (int i = 0; i < k; i++) {
		cin >> v[i];
	}

	int l = 1; // 심판 간 최소 거리
	int r = v[k - 1] - v[0]; // 심판 간 최대 거리
	string ans = "";

	while (l <= r) {
		int mid = (l + r) / 2; // 현재 loop의 심판 간 거리

		int x = v[0];
		int cnt = 1; // 배치된 심판의 수
		string cur_ans = "1";
		for (int i = 1; i < k; i++) {
			// 심판을 배치할 수 있는 경우만 처리
			if (v[i] - x >= mid && cnt < m) {
				cnt++;
				x = v[i];
				cur_ans += "1";
			}
			else
				cur_ans += "0";
		}

		// 심판이 옳게 배치된 경우 최소 거리를 늘리고 정답 갱신
		// 최소 거리 증가(더 적합한 답이 있는지 탐색)
		if (cnt == m) {
			l = mid + 1;
			ans = cur_ans;
		}
		// 심판이 너무 적게 배치된 경우 최대 거리를 줄인다.
		else {
			r = mid - 1;
		}
	}

	cout << ans;
}