[C++] 백준 1508번: 레이스

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

1508번: 레이스

 

 > 접근

심판들의 거리가 '특정 값' 이상일 때 배치해야한다고 강제하고, 이 특정 값을 이분탐색으로 찾는다.

이분탐색의 범위를 0~N으로 두고, 이 범위 내에서 적절한 값을 찾아내야한다. 이를 위해선, start = mid + 1 또는 end = mid - 1를 언제 수행해야할지를 결정해야한다. 조금 추상적으로 생각해보면, mid값(=특정 값)이 너무 클 경우에는 심판을 배치를 적게 하게 될 것이며, 작을 경우에는 심판을 많이 배치하게 될 것이다. 이를 위해 mid값이 주어졌을 때 이를 기준으로 심판을 선택하는 코드를 짠다. 이 때 선택할 때마다 카운트를 증가시켜서 이분탐색을 완성시킨다. 또한, 0과 1로 구성된 출력값을 이 때 동시에 만들어낼 수 있다.

그리고 사전순으로 가장 뒤에 있는 값을 출력하라고 되어있으므로, 맨 처음 심판을 선택하도록 강제하고, 심판을 선택할 때 앞에서부터 진행한다. 또한 가장 마지막에 갱신된 cur값(mid에 따라 선택된 출력값)을 결과로서 출력한다.

 

#include <bits/stdc++.h>
using namespace std;

int N, M, K;
int positions[50];

void solution() {
	string res;

	int start = 0;
	int end = N;

	while (start <= end) {
		int mid = (start + end) / 2;
		
		// 사전상 늦은 순서를 출력해야하므로 첫번째 자리를 선택을 강제한다.
		string cur = "1";
		int selected = 1;
		int prev = 0;
		
		// Set cur
		int i;
		for (i = 1; i < K; i++) {
			if (positions[i] - positions[prev] >= mid) {
				cur += "1";
				selected++;
				prev = i;

				if (selected == M) break;
			}
			else {
				cur += "0";
			}
		}

		// 오른쪽에 0 채우기(M번 선택해서 중간에 빠져나올 경우)
		while (cur.size() < K) cur += "0";

		// 충분히 많이 선택했을 때는 mid값을 증가시킨다.
		if (selected == M) {
			start = mid + 1;
			res = cur;
		}
		// vice versa
		else {
			end = mid - 1;
		}
	}

	cout << res;
}

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

	int i;
	cin >> N >> M >> K;
	for (i = 0; i < K; i++) cin >> positions[i];

	solution();

	return 0;
}