1. 문제
1) 문제 링크
: 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
2) 설명
수평선 위에 N개의 집이 있고 N개의 집에 C개의 공유기를 설치하는 문제.
문제에서 말하는 "가장 인접한 두 공유기 사이의 거리를 최대로 하는" 이 조금 이해하기 힘들었지만 결국
공유기가 설치된 집들 간의 거리의 최소값을 최대로 만들면 된다.(말이 조금 어렵다)
예를 들어
| index | 0 | 1 | 2 | 3 | 4 | 5 |
| 위치 | 1 | 3 | 8 | 10 | 14 | 20 |
| 공유기 설치 | O | X | X | O | X | O |
위와 같은 상황이라면 답은 0번째 집, 3번째 집, 5번째 집에 설치를 해서 공유기가 설치된 이웃집 간 최소 거리의 최대값인 9 ( maximize( min( dist(house[0], house[3]), dist(house[3], house[5]) ) ) ) 이 된다.
2. 풀이
1) 알고리즘
: 이분탐색
2) 풀이 설명
공유기가 설치된 이웃집 거리는 1에서 (수평선에서 가장 오른쪽 집과 가장 왼쪽 집 거리) 범위 안에 있을 수 있다.
그래서 그 거리를 구하기 위해 + 이분 탐색을 위해 houses(집 위치 벡터)를 정렬해준다.
이후 이분탐색을 통해서 최소 거리의 최대값을 찾아나간다.
이때 getMinDist 함수를 통해서 인자로 입력받은 거리 이상으로 공유기 설치가 가능한지 판단하고 불가능하다면 -1을, 가능하다면 그때의 거리 최소값(인자로 입력받은 거리 이상의)을 리턴해주도록한다.
getMinDist 함수에서 첫 번째 집(가장 왼쪽)은 반드시 공유기를 설치한다고 가정한다. 그 이유는 다음과 같다.
처음 공유기가 설치되는 집이 x번째 ( x > 1 )라고 해보자. 그러면 x번쨰 집(hosues[x])과 그 다음 공유기가 설치된 집(houses[x + n]) 간의 거리는
1. 공유기가 설치된 집 중 가장 가까운 거리
2. 공유기가 설치된 집 중 가장 가깝지는 않은 거리
중 하나다.
당연한 말 같아보이지만 첫 번째 집에 공유기를 설치해야되는 이유를 설명하는 데 이 두 가지 경우를 나눠서 생각하는 게 필요하다고 생각한다.
이제 x번째 집에서 공유기를 제거하고 첫 번째 집(houses[0])에 공유기를 설치한다고 생각해보자.
그러면 그 다음 공유기가 설치된 집(houses[x + n])과 첫 번째 공유기가 설치된 집(이제는 houses[0]) 사이의 거리는 공유기를 x번째에 설치했을 때보다 멀어질 것이다.
그러면 위의 1번의 경우에는 공유기가 설치된 집 간 거리 중 최소값이 증가하게 된 것이니까 답을 잘못 구한 게 된다.(더 큰 최소값을 찾을 수 있다는 말)
그리고 2번의 경우에는 이 첫 번째 공유기가 설치된 집과 두 번째 공유기가 설치된 집 사이의 거리가 늘어나도 어차피 최소 거리보다는 크기 때문에 전혀 상관이 없다.
결론적으로 문제에서 요구하는 "가장 인접한 두 공유기 사이의 거리를 최대로 하는 집들"을 선택했을 때 그 시작이 첫 번째(houses[0])집이 아니라면 1번의 경우에는 더 큰 최소값이 있으므로 답을 잘못 구한 게 되고 2번의 경우에는 첫 번째 집을 고르든 말든 전혀 상관이 없다는 말이다. 즉 첫 번째 집에 무조건 공유기를 설치했다고 가정하는 것은 답을 구하는 데 충분조건으로 작용한다는 말이다.
이 논리는 반대로 마지막 집에도 똑같이 적용된다.
또한 사실 getMinDist 함수를 인자로 받은 거리로 공유기 설치가 가능한지만 판단해줘도 되는데 모든 집 사이의 거리가 넓은 경우에 시간을 더 단축할 수 있지 않을까 해서 인자로 받은 거리 이상의 거리(즉 공유기가 설치된 집 간의 거리가 인자로 받은 거리 이상으로 위치하게 하는 실제 거리)를 리턴하도록 해주었다. (근데 속도를 보니 크게 시간 단축의 효과는 없는 것 같았다ㅠㅠ)
3. 코드
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long LL;
const LL MAX_VAL = 999999999;
LL N, C;
vector<LL> houses;
LL getMinDist(LL minDist){
LL answer = MAX_VAL;
int prevHouse = 0; // 이전 집과의 거리를 구하기 위해 이전 집의 index를 저장해놓을 변수
LL numOfAP = 1; // 설치된 공유기의 개수. 첫 집에 설치된 상태에서 시작하기 때문에 초기값 1
for(int i=1;i<houses.size() && numOfAP<=C;i++){
if(houses[i] - houses[prevHouse] >= minDist){
//집 간 거리가 인자로 받은 최소거리보다 크다면 업데이트
answer = min(answer, houses[i] - houses[prevHouse]); // 거리 업데이트
prevHouse = i; // 이전 집 index 업데이트
numOfAP++; // 설치된 공유기 개수 증가
}
}
if(numOfAP < C){
//공유기를 적게 놓았으면 -1 return
return -1;
} else {
return answer;
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
LL input, answer = 0;
cin >> N >> C;
houses.reserve(N);
for(int i=0;i<N;i++){
cin >> input;
houses.push_back(input);
}
//sort
sort(houses.begin(), houses.end());
//binary search
LL s = 0;
LL e = houses.back() - houses.front();
while(s<=e){
LL mid = (s + e)/2;
LL minDist = getMinDist(mid);//mid 이상의 거리의 최소값을 구함
if(minDist >= mid){
s = minDist + 1;
answer = max(answer, minDist);// 최소 거리의 최대값을 구해야 하므로 minDist >= mid 일 때만 업데이트
} else {
e = mid - 1;
}
}
cout << answer << endl;
return 0;
}
4. 느낀점
이분탐색은 자주 구현해도 어려운 것 같다...
'알고리즘 > 백준' 카테고리의 다른 글
| [백준/7512] 연속하는 소수의 합 (0) | 2021.09.20 |
|---|---|
| [백준/1727] 커플 맞추기 (0) | 2021.08.25 |
| [BOJ/1034] 램 (0) | 2021.07.27 |
| [BOJ/7579] 앱 (0) | 2020.12.29 |
| [BOJ/14891] 톱니바퀴 (0) | 2020.12.18 |
