[이진탐색] BAEKJOON '2110'번 ' 공유기 설치 '문제 (C++/python)

문제 : www.acmicpc.net/problem/2110

2110번: 공유기 설치

 

 

 

• 문제 해결 아이디어

    1.  좌표의 최대 수가 10억이므로, 이진 탐색을 통해 공유기 사이의 거리를 구하여야된다.

   

    2.  집의 개수가 N 좌표가 X라 할 때, 최대 O( N log(X) )가 걸린다.

   

    3.  인접한 공유기 사이의 거리를 변수로 두고, 그 값을 이진탐색을 통해 바꾸어가며, 인접한 공유기 사이의 거리의 최대값을 구한다.

 

 

 

 

 

예제입력

5 3
1
2
8
4
9

 

우선 입력받은 값을 오름차순으로 정렬한다.

 

이후, 현재 공유기 사이의 거리가 최대인 경우와 최소인 경우를 각각 저장한다.

 

 

 

이진탐색을 위해 현재 gap을 middle_gap으로 잡고 공유기 설치가 가능한지 살펴보면

 총 두개만 설치되기 때문에, 설치가 불가능하다.

 

 

 

 

모든 공유기를 설치하기 위해선, 현재 gap (middle_gap)보다 gap의 크기가 작아야된다는 얘기이므로, max_gap을 middle_gap - 1로 바꿔준 후 설치가 가능한지 다시 확인한다. 

 

 

현재 gap이 2가 되었을 때, 3개의 공유기가 설치 가능하므로 result에 2를 저장해준 후, min_gap을 middle_gap보다 1증가시켜준다. ( 현재 gap보다 더 커도 조건을 만족하는지 확인하기 위해서. )

 

 

 

 

 

현재 gap이 3일 때에도 3개의 공유기가 설치 가능하므로 result에 3을 저장해주고, 다음으로 넘어가지만, 이때 min_gap이 max_gap보다 커지게 되므로, 과정을 끝내고 result를 출력한다.

 

 

 

 

• python

n, c = list(map(int, input().split(' ')))

arr = []
for _ in range(n):
    arr.append(int(input()))
arr = sorted(arr)

gap_min = arr[1] - arr[0]
gap_max = arr[-1] - arr[0]
result = 0

while(gap_min <= gap_max):
    gap_middle = (gap_min + gap_max) // 2
    start = arr[0]
    cnt = 1
    for i in range(1, len(arr)):
        if arr[i] >= start + gap_middle:
            start = arr[i]
            cnt += 1
    if cnt >= c:
        gap_min = gap_middle + 1
        result = gap_middle
    else:
        gap_max = gap_middle - 1

print(result)

 

 

• c++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> v;


int main(){
    
    int n, c, cnt, gap_min, gap_max;
    int result=0;
    scanf("%d %d", &n, &c);
    
    for(int i= 0 ; i< n ; i++){
        int tmp;
        scanf("%d",&tmp);
        v.push_back(tmp);
    }
    
    sort(v.begin(), v.end());
    
    gap_min = v[1] - v[0];
    gap_max = v[v.size()-1] - v[0];
    
    while(gap_min <= gap_max){

        cnt = 0;
        int gap_middle = (gap_min + gap_max) /2;
        int start = v[0];
        
        for(int i=0 ; i< n ; i++){
            if(start + gap_middle <= v[i]){
                cnt++;
                start = v[i];
            }
        }

        if(cnt >= c-1){
            gap_min = gap_middle + 1;
            result = gap_middle;
            
        }
        else{
            gap_max = gap_middle-1;
        }

    }
    printf("%d\n",result);
    
    
    return 0;
}