코딩테스트 연습
[BOJ] 2110. 공유기 설치 (binary_search, parametric_search)
hio9_9
2023. 1. 23. 03:56
Gold IV
https://www.acmicpc.net/problem/2110
2110번: 공유기 설치
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가
www.acmicpc.net
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
input:
- 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다.
- 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
output:
- 첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
Idea :
- 처음에는 dfs를 생각했지만.. N값을 보면 당연히 시간초과가 나올 수 밖에 없다..!
- 결국 hint와 다른 코드를 참고해서 binary search이고 기준이 공유기 사이 거리임을 알 수 있었음
- binary search
- 찾고자 하는 값 = C개 이상 설치했을 때의 공유기 사이 거리 최댓값 → 기준 = 공유기 사이 거리
- init - start = 거리 최솟값 = 1, end = 거리 최댓값 = 마지막 집 위치 - 첫 번째 집 위치
- start와 end의 중간값 mid를 공유기 사이 거리로 했을 때
- C개 이상 설치가 가능하면,
공유기 사이 거리 최댓값을 찾기 위해 (mid + 1 ~ end) 로 binary search 반복 - C개 이상 설치가 불가능하면,
C개 이상 설치가 가능한 거리를 구해야 하므로 (start ~ mid -1) 로 binary search 반복
- C개 이상 설치가 가능하면,
Code :
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, C;
vector<int> houses;
int answer = 0;
/* checker: 공유기 사이 거리기 dist로 했을 때 설치할 수 있는 개수를 구하고
* 설치해야 하는 개수 조건 C를 충족하는지 확인하는 함수
*
* parameter - dist: 공유기 사이 거리
* return - dist를 사이 거리로 공유기를 설치했을 때 설치 가능한 개수가 C 이상이면 true, C 미민이면 false
*/
bool checker(int dist) {
vector<int>::iterator prev = houses.begin();
int wifi_cnt = 1; // 설치한 공유기 개수
for (auto cur = houses.begin()+1; cur < houses.end(); cur++) {
if (*cur - *prev < dist) continue;
// prev 집과 cur 집 사이 거리가 dist 이상일 경우
wifi_cnt++;
prev = cur;
// 공유기 설치 개수 >= C
if (wifi_cnt >= C) return true;
}
// 공유기 설치 개수 < C
return false;
}
/* binary_search: 이분 탐색으로 가장 인접한 두 공유기 사이 거리의 최댓값을 구하는 함수
*
* parameters - min_dist: 공유기 사이 거리 최솟값
* - max_dist: 공유기 사이 거리 최댓값
* no return
*/
void binary_search(int min_dist, int max_dist) {
if (min_dist > max_dist) return; // wrong range
int mid = (min_dist + max_dist) / 2;
// mid가 공유기 사이 거리일 때, C개 설치를 할 수 없으므로 거리를 더 줄여야 됨
if (!checker(mid))
binary_search(min_dist, mid-1);
// mid가 공유기 사이 거리일 때, C개 이상 설치할 수 있으므로 거리를 더 늘려야 됨
else {
answer = max(answer, mid);
binary_search(mid+1, max_dist);
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
// freopen("input.txt", "rt", stdin);
cin >> N >> C;
for (int i=0; i<N; i++) {
houses.push_back(0);
cin >> houses[i];
}
sort(houses.begin(), houses.end());
binary_search(1, houses[N-1] - houses[0]);
cout << answer << "\n";
}
Result :
메모리: 3688 KB, 시간: 32 ms
Review :