백준 - 2110번 : 공유기 설치 (C++)

풀이 방법 : 이분 탐색 , 매개 변수 탐색

정렬 가능한 1차원 배열에 대해 최대 혹은 최솟값을 구하는 경우 매개 변수 탐색을 고려해보자.

매개 변수 탐색을 고려할 때 중요한 것은 정답을 매개 변수화할 수 있는지, 매개변수에 따라 참인지 거짓인지를 따질 수 있는지다.

문제에서 요구하는 값(두 공유기 사이의 간격)을 매개변수로 삼아 문제를 풀어보면

1. 오름차순으로 집 좌표들 정렬

2. 설치한 공유기 사이에서 가능한 가장 가까운 거리(Min = 0), 가장 먼 거리(Max == N번째 집 - 첫 번째 집)를 구한다.

3. Min과 Max를 이용해 Mid값을 구해서 탐색 시작

4. 먼저 첫 번째 집에 설치 후 그 다음 집들을 탐색해가며 그 거리가 Mid 이상인 집을 만나면 Cnt를 증가시킨다.

5. Mid 이상인 집을 만났다면 비교 대상을 해당 집으로 바꾸고 다시 그로부터 Mid 이상인 집이 있는지 탐색한다.

6. Cnt가 C개 이상이라면 답을 갱신시키고 좀 더 느슨한 간격으로 해도 된다는 뜻이므로 Min = Mid + 1로 갱신, Cnt가 C개 미만이라면 좀 더 촘촘한 간격으로 탐색해야 한다는 뜻이므로 Max = Mid - 1로 갱신

7. Min <= Max를 만족하는 동안 3 - 6 반복

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int N, C;
	cin >> N >> C;

	vector<int> vecHome(N);

	for (int i = 0; i < N; ++i)
	{
		cin >> vecHome[i];
	}

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

	int Min = 0;
	int Max = vecHome[N - 1] - vecHome[0];

	int Answer = 0;

	while (Min <= Max)
	{
		int Current = 0;
		int Mid = (Min + Max) / 2;

		int Cnt = 1;

		for (int i = 1; i < N; ++i)
		{
			if (vecHome[i] - vecHome[Current] >= Mid)
			{
				++Cnt;
				Current = i;
			}
		}

		if (Cnt < C)
		{
			Max = Mid - 1;
		}

		else 
		{
			Answer = max(Answer, Mid);
			Min = Mid + 1;
		}
	}

	cout << Answer;
}

이분 탐색은 어떤 기준으로 변수의 범위를 좁혀나갈 것인지만 잘 생각하면 쉬워지는 것 같다.
물론 그게 어려워서 미칠 것 같다...