백준/2110번/공유기 설치/골드4

July 10, 2023

카테고리: CodingTest

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

문제 설명

Site: Baekjoon
Number: 2110
Category: 이분탐색, 매개변수 탐색
Rank: Gold 4

N개의 집에 C개의 공유기를 설치한다. (N의 범위 2 ≤ N ≤ 200,000, C의 범위 2 ≤ C ≤ N)

이 때 가장 인접한 두 공유기의 거리의 최댓값, 즉 공유기 사이의 거리 중 최솟값의 최대를 구하는 문제이다.

매개변수 탐색 문제이므로, 매개변수 탐색 문제를 풀이할 때 스텝을 밟으며 풀이하면 된다.

매개변수 탐색 문제

문제를 역으로 생각하여 True / False문제로 생각한다
- 2110번 문제의 경우 N개의 집에 C개의 공유기를 설치하여 가장 인접한 공유기 거리의 최댓값의 문제를 역으로 생각하여 거리 D를 정하였을 때 C개의 공유기가 설치 가능한지 확인한다.
입력값의 배열을 (False—— / True——)같이 어느 특정한 지점(정답)에서 False가 True로 바뀌게 정렬한다.
Low와 High의 초깃값을 설정한다. (초깃값이 조금만 벗어나도 틀릴 수 있으므로 주의한다)
- 초깃값을 정하는 방법은 2110번의 경우 Low는 가능한 가장 적은 거리인 1, High는 불가능한 거리 중 가장 작은 값인 마지막 집에서 첫번째 집의 거리를 뺀 값에 1을 더한 값이다.
True와 False를 판별한 함수를 만들어 while문을 통해 정답을 구한다.
- 2110번의 경우 D의 거리를 주었을 때 C만큼의 공유기를 설치할 수 있는지가 판별할 함수이다.
- while문을 실행하며 low와 high값을 갱신할 때에도 low는 가능한 값, high는 불가능한 값으로 갱신해야한다.

#include <iostream>
#include <algorithm>

using namespace std;

int arr[200001];

//매개변수 범위 판별 함수
bool Check(const int& D, const int& N, const int& C)
{
	//cnt = 공유기를 설치한 집의 갯수, cur = 마지막으로 공유기가 설치된 집의 index
	int cnt = 1, cur = 0;

	//첫 집부터 공유기를 설치하며 만약 index가 j인 집과 cur인 집의 거리 차이가 D보다 크거나 같다면 cur을 마지막으로 공유기가 설치된 j로 바꾸어주고 공유기를 설치한 집의 갯수를 하나 늘린다.
	for (int j = 0; j < N; j++)
	{
		if (arr[j] - arr[cur] >= D)
		{
			cnt++;
			cur = j;
		}

		//그렇게 설치된 집의 갯수가 C보다 크거나 같다면 거리 D는 가능한 거리이므로 true를 리턴한다.
		if (cnt >= C)
			return true;
	}

	//거리 D는 불가능한 거리이므로 false를 리턴한다.
	return false;
}


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

	int N, C;
	cin >> N >> C;

	for (int i = 0; i < N; i++)
		cin >> arr[i];

	sort(arr, arr + N);


	int low = 1, high = arr[N - 1] - arr[0]+1;

	while(low + 1 < high)
	{
		int mid = (high + low) / 2;

		//low와 high를 갱신할때 Check가 true라면 mid는 가능한 거리이므로 low = mid, false라면 mid는 불가능한 거리이므로 high = mid가 된다.
		if (Check(mid, N, C))
			low = mid;
		else
			high = mid;
	}

	cout << low;

	return 0;
}

백준2110

평생하는 개발 공부

문제 설명