BOJ 2110) 공유기 설치

Binary Search의 기본이 되는 문제라고 할 수 있다!

기본적으로 이분 검색 문제는 눈에 보이게 뻔하게 내는 경우가 없다.

이분 검색 문제는 보통 답을 이분 검색으로 검색해야하는 상황에서 나오는 경우가 많은데 사실 이 상황을 인지하기는 쉽지 않은 것 같다.

https://www.acmicpc.net/problem/1981

이 문제도 이분 검색 문제의 일환으로 BFS와 Binary Search이 혼합되어 있는 문제이다.

일단 나중에 이 문제를 풀어보도록 하고

2110번인 공유기 설치 문제부터 풀어보도록 하자.

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


문제 요약

직선 위에 점 N개가 있다. 점 N개 중에 C개를 선택하여야 하는데 다음과 같은 조건이 있다.
선택된 점들 중에 인접한 점의 거리가 최대로 하는 프로그램을 작성해야 한다.

입력

첫째 줄에 점의 갯수 N ( 2 <= N <= 200000)과 선택할 점의 갯수 C (2 <= C <= N)를 주어지고 둘째 줄부터 N개의 줄에는 점의 좌표를 나타내는 $$x_i$$가 주어진다. (1 <= $$x_i$$ <= 1000000000)

출력

첫째 줄에 가장 인접한 선택된 두 점의 최대 거리를 출력한다.

--------------------------------------------------------

먼저 내가 접근하려했던 방향은 DP를 이용하여 접근하려 했다.
근데 공유기의 갯수가 2 <= C <= N임을 깨닫고 Time Complexity가 O(NC)이므로 불가능하다는 것을 깨달았다.

문제는 이러한 선택된 점들의 거리를 계산하기 위해서는 시뮬레이션 작업이 필수라는 작업이다. 허나 점의 갯수가 200000이여서 log단위의 반복이 없으면 불가능하다는 것을 깨달았다.

그렇다면 우리가 다음과 같이 접근해볼 수도 있다.

가장 인접한 선택된 두 점의 최대 거리를 미리 정해놓는 것을 어떨까?

즉 가장 인접한 선택된 두 점의 최대 거리를 정해놓고 주어진 점이 정해진 최대 거리를 만족하지 못할 경우 이분 검색을 통해 범위를 줄여나가는 것이다!

이럴 경우 Time Complexity는 O(N * log( max(x_i))로 제한 시간에 AC를 받을 수 있다.

즉, 여기서 포인트는 가장 인접한 두 점 사이의 거리를 정해놓는다는 점.

또한 이분 검색을 통해 해당 최대 거리를 갱신한다는 점에 있다.

--------------------------------------------------------------------

풀 코드는 깃헙에 추가한다.

https://github.com/shingiyeon/baekjoon/blob/master/2110.cpp

bool find_pos(int c){

int num = 1;

int idx = 1;

int x = v[0];

while(idx < N){

if ( v[idx] - x >= c){

num++;

x = v[idx];

idx++;

}

else{

idx++;

}

}

if(num >= C){

return 1;

}

else{

return 0;

}

}

void find_max(int s, int e){

if(s>e) return;

int mid = (s+e)/2;

if(find_pos(mid)){

MAX = mid;

find_max(mid+1, e);

}

else{

find_max(s, mid-1);

}

}