문제
풀이
이분 탐색을 사용한다. 공유기를 설치할 간격을 이분 탐색으로 좁혀서 진행한다.
- 집의 좌표를 오름차순으로 정렬한다.
- 공유기를 설치할 수 있는 최소 간격과 최대 간격을 구한다.
- 최소 간격: 집 사이의 최소 거리인 1
- 최대 간격: 마지막 집과 처음 집 사이의 거리
- 설치할 간격을 이분 탐색으로 좁혀서 진행한다.
- 첫 집은 무조건 설치한다.
- 설치할 간격인 mid만큼 거리를 벌려서 공유기를 설치했을 때, 설치한 공유기의 수가 C이상인 경우 간격을 늘리고, 미만인 경우 간격을 줄인다.
- 설치한 공유기 수가 C를 만족한 경우 답을 갱신한다.
코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(nullptr);
int N, C;
vector<int> house;
cin >> N >> C;
for (int i = 0; i < N; ++i)
{
int temp;
cin >> temp;
house.push_back(temp);
}
sort(house.begin(), house.end());
// 공유기를 설치할 수 있는 최소 거리인 1
// 최대 거리인 첫 집에서 마지막 집 까지의 거리
// 공유기를 설치할 간격을 줄여나가면서 이분 탐색을 진행한다.
// 설치한 공유기의 수가 N을 충족한다면 answer를 갱신한다.
int start = 1;
int end = house[N - 1] - house[0];
int answer = 0;
while (start <= end)
{
int mid = (start + end) / 2;
// 첫번째 집은 무조건 설치한 상태로 진행한다.
int router = 1;
int pre_house = house[0];
// 가장 최근에 설치한 집과의 거리가 mid보다 클 경우
// pre_house를 갱신하고 공유기 설치수를 증가시킨다.
for (int i = 1; i < N; ++i)
{
if (house[i] - pre_house >= mid)
{
router++;
pre_house = house[i];
}
}
// C보다 많은 공유기를 설치했다면
// start를 늘려서 설치할 거리를 늘린다.
if (router >= C)
{
start = mid + 1;
answer = max(answer, mid);
}
else
{
end = mid - 1;
}
}
cout << answer;
return 0;
}
'알고리즘 > 백준' 카테고리의 다른 글
[백준][C++] 2343: 기타 레슨 (1) | 2023.10.26 |
---|---|
[백준][C++] 16564: 히오스 프로게이머 (1) | 2023.10.23 |
[백준][C++] 2342: Dance Dance Revolution (0) | 2023.10.21 |
[백준][C++] 2252: 줄 세우기 (1) | 2023.10.20 |
[백준][C++] 2143: 두 배열의 합 (1) | 2023.10.19 |