[이분탐색] 공유기 설치(2110)(C++)

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

2110번: 공유기 설치

 

1. 문제 개요

 

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

 

 

2. 입출력

 

 

3. 문제 풀이

 

도현이의 집들의 일차원 좌표와 공유기의 개수가 주어질 때, 공유기 사이의 거리의 최솟값이 최대가 되도록 하는 문제이다. 이분탐색을 통해 구할 수 있다. 공유기는 최소 두 개, 최대 N(집의 수)만큼 주어지므로 집 간격의 최솟값은 1, 최대값은 가장 멀리 떨어져있는 두 집의 거리가 되게 된다.

 

따라서 인풋으로 집의 좌표가 들어오면, 이를 정렬하고, left=1, right=house[N-1]-house[0] 으로 설정한 후 이분탐색을 시작한다.

이때, 중앙값( mid=(left+right)/2 )이 조건을 만족하면 더 높은 수로 탐색하고, 조건을 만족하지 않으면 더 낮은 수로 탐색한다.

 

이 때, 조건을 만족한다는 것은, 왼쪽부터 차례로 간격이 mid 이상이 되도록 공유기를 설치해보며, 문제에서 주어진 값 이상을 설치할 수 있는 지를 확인하면 된다.

 

 

4. 전체 코드

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <math.h>

using namespace std;


int main(void) {

    int N, C;
    scanf("%d%d",&N,&C);
    
    vector<int> house;
    
    for(int i=0;i<N;i++) {
        int temp;
        scanf("%d",&temp);
        house.push_back(temp); // 집들의 좌표를 입력으로 받는다.
    }

    sort(house.begin(), house.end()); // 집들을 오름차순으로 정렬한다.
    
    int left = 1;
    int right = house[N-1]-house[0]; // right 값을 최대 거리로 설정한다.
    
    while(left<=right) {
        int mid = (left+right)/2;
        int cnt = 1,cmp = house[0];
        
        for (int i=1; i<N; i++) { // 조건을 만족하는지 알아본다.
            if (house[i]-cmp>mid) {
                cnt++;
                cmp = house[i];
            }
        }

        if(cnt>=C)
            left = mid + 1;
        else
            right = mid - 1;
    }
    
    printf("%d",left);
    
}

아직 배워가는 중이라 틀린 부분이 있을 수 있습니다. 지적할 부분이 있다면 댓글로 알려주시면 감사하겠습니다!!!