[백준/BOJ] 백준 1508번 : 레이스

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

1508번: 레이스

이분 탐색, 파라메트릭 서치, 결정 문제로 가까운 두 심판의 거리가 mid 길이 만큼이 가능한지 판단해서 가까운 심판의 거리가 최대가 될 때 배치를 구했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, m, k;
vector<int> human;

//가까운 두 심판의 거리가 gap 길이 만큼 일때 심판 m명을 배치하는게 가능한지 확인
//가능하다면 배치 표시를 반환
vector<int> Decision(int gap)
{
	vector<int> ret;
	int limit = -1;
	int cnt = 0;

	for (int i = 0; i < human.size(); i++)
	{
		//human[i]자리에 심판을 배치할 수 있다면 심판을 배치한다
		if (limit <= human[i])
		{
			cnt++;
			limit = human[i] + gap;
			ret.push_back(1);

			//심판을 m명 모두 배치했다면 나머지 곳은 모두 심판을 배치하지 않아 0으로 채운다
			if (cnt == m)
			{
				while (ret.size() != human.size())
					ret.push_back(0);

				break;
			}
		}

		//human[i]자리에 심판을 배치할 수 없을때
		else
			ret.push_back(0);
	}

	//심판 m명을 배치할 수 있을때
	if (cnt == m)
		return ret;

	ret.clear();
	return ret;
}

//결정 문제로 가까운 두 심판의 거리가 mid 길이 만큼이 가능한지 판단하였다 
vector<int> Solve()
{
	int left = 0;
	int right = n;
	vector<int> temp_ret;
	vector<int> ret;

	while (left <= right)
	{
		int mid = (left + right) / 2;

		temp_ret = Decision(mid);

		//가까운 두 심판의 거리가 mid 길이 만큼이 가능할때
		if (temp_ret.size() != 0)
		{
			left = mid + 1;
			ret = temp_ret;
		}

		//가까운 두 심판의 거리가 mid 길이 만큼 불가능 할때
		else
			right = mid - 1;
	}

	return ret;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int temp;
	vector<int> result;

	cin >> n >> m >> k;

	for (int i = 0; i < k; i++)
	{
		cin >> temp;
		human.push_back(temp);
	}

	result = Solve();

	for (int i = 0; i < result.size(); i++)
		cout << result[i];

	return 0;
}