[ BOJ 백준 2110번 - 공유기 설치 ] 해설 및 코드

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

 

 

 

목적

N개의 집 중에서, C개의 집에만 와이파이를 설치했을 때, 인접한 두 공유기의 거리를 최소로 만들자.

 

접근법

 

1. 이분 탐색 알고리즘을 이용하여 인접한 공유기의 최소 거리를 결정해 나간다.

 

• 가장 처음에 left는 1(가능한 최소 거리), right는 9(가능한 최대 거리)로 하여, 이분 탐색할 범위를 정한다. left와 right의 중간 값인 5를 최소 거리로 정한 후, 5이상의 간격으로 공유기 3개를 설치할 수 있는지 확인한다.

 

 

 

• 확인 후에는 범위를 좁혀야 하는데, 설치 가능 여부에 따라 중간 값을 기준으로 왼쪽, 오른쪽으로 범위를 갱신한다.

 

 

• 이런 과정을 left가 right보다 커질 때까지 반복하자.

2. 공유기 설치 가능 여부를 확인하기 위해서는 집의 좌표가 저장된 배열을 정렬된 형태로 사용해야한다.

 

#include<iostream>
#include<algorithm>
using namespace std;
 
int n,c,a[(int)2e5+1];
 
bool isPossible(int dist){
    int prev=a[0],cnt=c-1;
    
    for(int i=1;i<n;++i){
        if(a[i]-prev>=dist){
            prev=a[i];
            --cnt;
            if(cnt==0)return true;
        }
    }
    return cnt==0;
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    
    cin>>n>>c;
    for(int i=0;i<n;++i)cin>>a[i];
    sort(a,a+n);
    
    int left=1,right=a[n-1];
    while(left<=right){
        int mid=(left+right)/2;
        
        if(isPossible(mid))left=mid+1;
        else right=mid-1;
    }
    
    cout<<right;
}
 

 

 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.