문제
도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.
도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.
C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.
입력
첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.
출력
첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
예제 입력 1
5 3
1
2
8
4
9
예제 출력 1
3힌트
공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를 3개 설치할 수 없다.
문제 요약:
입력받은 집의 수 만큼 집의 좌표를 입력받아 C개의 공유기를 설치할 때 C개의 공유기를 적절히 설치해서 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.
🤔 생각할 점 :
- C개의 공유기를 모두 설치해야한다.
- 집이 꼭 바로 옆에 붙어 있지 않아도 된다.
- 집 좌표가 순서대로 들어오지 않음→ 오름차순 정렬
- 찾아야 하는 것 : 집들 사이의 거리
풀이 방법 :
-
N: 집의 수 ,C: 공유기 수 ,house: 집 좌표 벡터 -
집 좌표를 입력받아서 오름 차순 정렬
-
집들 사이 거리를 기준으로 이진 탐색
start는 집들 사이의 최소 거리 1로 초기화하고 , end는 집들 사이의 최대 거리(끝집 - 첫집의 거리)로 초기화한다.
-
중간값을 기준으로 공유기를 설치할 수 있는지 확인, 설치 가능하면
- start = mid + 1 → 탐색범위를 중간을 기준으로 오른쪽으로 이동, 최적의 거리를 업데이트 해준다.
- 설치할 수 없다면 end = mid - 1 → 탐색범위를 중간을 기준으로 왼쪽으로 좁힌다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, C;
int result = 0;
vector<int> house;
int binarySearch() {
int start = 1;
int end = house[N - 1]-house[0];
int result = 0;
while (start <= end) {
int mid = (start + end) / 2;
int count = 1;
int temp = 0;
for (int i = 1; i < N; i++) {
if ((house[i] - house[temp]) >= mid) {
temp = i;
count++;
}
}
if (count >= C) {
result = mid;
start = mid + 1;
} else {
end = mid - 1;
}
}
return result;
}
int main() {
cin >> N >> C;
for (int i = 0; i < N; i++) {
int x;
cin >> x;
house.push_back(x);
}
sort(house.begin(), house.end());
result = binarySearch();
cout << result << endl;
return 0;
}🌟메인 함수
int main() {
cin >> N >> C;
for (int i = 0; i < N; i++) {
int x;
cin >> x;
house.push_back(x);
}
// 1. 좌표 정렬
sort(house.begin(), house.end());
// 2. 집들 사이 거리에 대한 이진 탐색
result = binarySearch();
cout << result << endl;
return 0;
}이진 탐색 함수
int binarySearch() {
//3. 초기화
//start-> 최소 거리인 1, end -> 집들 사이 최대 거리(맨 끝집 - 맨 첫집)
int start = 1;
int end = house[N - 1]-house[0];
int result = 0;
//4. 탐색
while (start <= end) {
int mid = (start + end) / 2;//중간값
//count = 중간값을 기준으로 한 구간에 설치할 수 있는 공유기 개수
int count = 1;
//temp = 가장 최근에 공유기를 설치한 집 인덱스
int temp = 0;
//한 구간에 대해 설치할 수 있는 공유기의 수를 센다.
for (int i = 1; i < N; i++) {
if ((house[i] - house[temp]) >= mid) {
temp = i;
count++;
}
}
//count가 주어진 공유기의 개수 C보다 크거나 같은 경우 탐색 범위를 오른쪽으로 좁힌다.
if (count >= C) {
result = mid;
start = mid + 1;
}
//그렇지 않은 경우에는 탐색 범위를 왼쪽으로 좁힌다.
else {
end = mid - 1;
}
}
return result;
}
