레이스(이분 탐색, 그리디)

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

1508번: 레이스

 

https://djgameprogramming.tistory.com/117

공유기 설치(이분 탐색, 그리디)

공유기 설치 문제와 거의 동일하게 접근하면 된다.

 

M개라는 설치 제한이 있으므로 제한 이후의 지점은 전부 설치가 불가능 함에 유의하여야 한다.

간격 값이 아닌 설치 현황을 제시하는 문제이므로

최대 간격 값이 업데이트 될때마다 설치 현황도 같이 업데이트 해주어야 한다.

 

공유기 설치 문제와 다른 부분은 주석처리를 해놓았다.

 

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

int N, M, K;
vector<int> Race;
bool Check[50];
// 간격에 따른 설치지점을 저장할 배열

int Solve(int mid)
{
	int ret = 1;
	int pre = Race[0];
	memset(Check, 0, sizeof(Check));
	Check[0] = true;
	for (int i = 1; i < K; i++)
	{
		if (Race[i] - pre >= mid)
		{
			ret++;
			Check[i] = true;
			if (ret == M) break; // 설치 제한 존재함
			pre = Race[i];
		}
	}
	return ret;
}

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

	cin >> N >> M >> K;
	int cmd = K;
	while (cmd--)
	{
		int tmp;
		cin >> tmp;
		Race.push_back(tmp);
	}

	int ret = 0;
	bool Ans[50] = { 0, }; // 답으로 제시할 배열
	int s = 1;
	int e = Race.back() - Race.front();
	while (s <= e)
	{
		int mid = ((s + e) / 2);
		if (Solve(mid) == M)
		{
			if (ret < mid)
			{
				ret = mid;
				memcpy(Ans, Check, sizeof(Ans));
				// 설치한 공간을 업데이트
			}
			s = mid + 1;
		}
		else e = mid - 1;
	}

	for (int i = 0; i < K; i++)
	{
		cout << (Ans[i]) ? 1 : 0;
	}
}