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

나는 이분탐색을 굉장히 싫어한다.
이상하게 이분탐색 문제들은 난이도에 비해 너무 어렵게 느껴진다.
그러므로 이번주는 이분탐색 특집으로 나를 일주일 동안 줘패기로 결심했다.

문제링크

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

설명

1~2시간 고민하고 질문글이랑 구글링해서 코드 찾아봤는데도 한 번에 이해하기 힘들어서 F11 눌러가면서 알고리즘 실행 과정을 천천히 살펴보고 나서야 이해가 되었다.

이 문제의 핵심은
1. 첫 번째 집에는 반드시 공유기가 설치된다는 점
2. 인덱스가 아닌 간격을 기준 잡아 이분 탐색을 해나가야 된다는 점
이라고 생각한다.

우선 설치되는 공유기의 최소 개수는 2개고, 처음과 끝에 설치했을 때가 최대거리가 되기 때문에 나는 맨 처음에 처음과 끝은 무조건 설치하고 그 다음에 어떻게 해야할 지를 계속 생각했었다.

끝은 무조건 설치는 안 해도 되더라.... (문제 예제에서도 그럼)

하지만 여기까지 생각한 이후로 진도가 나가지 않아서 질문글을 뒤져보다가 발견한 것이 맨 처음은 무조건 설치되므로, 왼쪽에서부터 공유기를 설치해 나간다는 아이디어였다.

이 아이디어를 통해 설치되어야 하는 공유기의 개수와 첫 점, 끝 점을 통해 가장 최적의 간격을 구한 후, 그 간격을 점점 줄여가면서 답을 구하려고 했으나 당연히 TLE를 받을 수 밖에 없는 아이디어라 결국 구글링을 했다.

구글링을 통해 본 다른 코드에서는 왼쪽에서부터 공유기를 설치해 나간다는 아이디어는 동일하나, 첫 점과 끝 점 사이의 간격을 이분탐색을 통해 줄여나간다는 점이 달랐다.

시작점이 끝점보다 커지지 않을 때까지 계속해서 최적의 해를 갱신해 나가면서 이분탐색을 진행하고 그 후 답을 출력한다.

이분탐색 문제인데 어째서 나는 이분탐색을 활용하지 않았는가.
내가 너무 이분탐색을 어려워하고 거부하니까 이를 어떻게 활용해야할 지 고민하지 않아서 풀이에 더 어려움을 느꼈던 거 같다.

이분탐색 문제를 많이 접해서 좀 익숙해지려고 노력해야겠다.

코드

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

using namespace std;

int main(void)
{
	int n, c, num, st, router, start, end, mid, ans = 0;
	cin >> n >> c;
	vector<int> pos;
	for (int i = 0; i < n; i++)
	{
		cin >> num;
		pos.push_back(num);
	}
	sort(pos.begin(), pos.end());
	start = 1;                             // 최소 거리
	end = pos[n - 1] - pos[0];             // 최대 거리

	while (start <= end)
	{
		router = 1;
		mid = (start + end) / 2;
		st = pos[0];

		for (int i = 1; i < n; i++)
		{
			if (pos[i] - st >= mid)
			{
				router++;
				st = pos[i];
			}
		}

		if (router >= c)
		{
			ans = max(ans, mid);
			start = mid + 1;
		}

		else
			end = mid - 1;
	}
	cout << ans;
	return 0;
}