[백준] 2110 공유기 설치

문제 : 

www.acmicpc.net/problem/2110

2110번: 공유기 설치

분석 :

이 문제는 내 기준선에서 조금 신박했던 (?) 이분(이진) 탐색 문제였다.

문제를 이해하는데에도 헷갈렸다. 처음에 정렬을 한 뒤 start 와 end 변수를 간격의 최소, 최대 거리로 설정해 둔뒤 이 위치를 mid 값 변경을 통해 index 위치를 변경 시킨 뒤 start 가 end 인덱스보다 커지게 되면 종료한다. 비교 기준은 mid 값으로 첫 집을 기준으로 for문을 돌며서 mid 값보다 크게 되면 router를 세운다. 다 돌고나면 세운 라우더의 갯수가 세우기로 명시된 라우터의 갯수보다 많은지 비교 하는데 크게 된다면 간격을 좁히기 위해 start 값을 mid 값 + 1로 설정한다.

즉, 공유기 갯수가 많다 --> 세울 간격을 좁힌다.  

공유기 갯수가 아직 모자라다 --> 간격을 넓혀 설치 수를 증가시킨다. 

후에 max_distance에는 마지막에 비교한 mid 가 곧 가장 먼 거리일테므로 이를 리턴한다.

 

c++ 코드 :

//
//  2110_router.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/02/09.


#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;

int find_min_distance(int home, int router, int *arr){
    int max_distance = 0;
    int start = 1; int end = arr[home - 1] - arr[0]; // 간격 최소, 최대 거리
    
    while(start <= end){
        int mid = (start + end) / 2;
        int set_router = arr[0]; //처음 세운 라우터
        int count = 1; // 처음 집 count
        
        for(int i = 1; i < home; i++){//첫집을 제외한 집을 돌면서 i 로 공유기 세움
            int compare = arr[i] - set_router;
            //가장 가까운 집 간격이 최소한 mid가 되도록 설정하기 위해서
            if(compare >= mid){ // 간격이 mid 보다 크다면 초기엔 end 쪽에 가까운 값으로 셋팅
                set_router = arr[i]; //초기 8로 셋팅
                count++;
            }
        }
        
        if(count >= router) {
            max_distance = mid;
            start = mid + 1;
        }else{
            //설치할게 남았으므로 설치 수 증가
            end = mid - 1; // 간격을 하나 감소 == 설치 수 증가
        }
    }
    return max_distance;

}


int main(){
    int home, router, distance;
    cin >> home >> router;
    int *arr = new int[home];
    for(int i = 0; i < home; i++){
        cin >> arr[i];
    }
    sort(arr, arr + home);
    distance = find_min_distance(home, router, arr);
    cout << distance << endl;
    return 0;
}

앞으로는 문제 풀면 바로 블로그에 올려야겠다. 문제 다시 보니 이해도 떨어진다 금붕어 같다