[백준/Baekjoon] 2110 공유기 설치 C++ :: Binary Search

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

2110번: 공유기 설치

---

1. Logic

이 문제에서 mid값은 공유기와 공유기 사이의 거리를 뜻한다. 이분탐색으로 공유기와 공유기 사이의 거리를 구한 후 

wifi[0]~wifi[n-1]까지 탐색하며 공유기간의 사이가 mid보다 큰거나 같을 때를 count해주며 count가 공유기 설치대수 m보다 크거나 같으면  start를 mid로 옮겨, 작으면 end를 mid로 옮겨 탐색해준다.

 

로직은 맞는 것 같은데 자꾸 WA가 나와서 뭐지 했는데 처음 탐색할 떄 end값을 잘못 넣어줘서 그랬던 것 같다. 가능한 범위가 1000000000까지 였는데 계속 wifi[n-1]을 넣어줘서 마지막 값이 이분탐색의 끝으로 가면 start값을 반환하기 때문에 정답에 항상 처리가 안 될 경우가 생겨서 그 부분을 처리해줬다.

---

2. Code

탐색 전 for문을 통한 처리

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

using namespace std;

long long n, m;
//long long maxDist = 0;

vector<long long> wifi;

bool check(long long mid) {
    long long prev = wifi[0];
    long long cnt = 1;
    
    for(long long i = 1; i < n; i++) {
        long long cur = wifi[i];
        if(cur - prev >= mid) {
            prev = cur;
            cnt++;
        }
    }
    
    if(cnt >= m) return true;
    else return false;
}

long long binarySearch() {
    long long start = 0;
    long long end = wifi[n-1];
    long long mid;
    
    if(end - start == 1) return 1;
    if(n == m) {
        int prev = wifi[0];
        int maxV = 0;
        for(int i = 1; i < n; i++) {
            if(wifi[i] - prev > maxV) {
                maxV = wifi[i] - prev;
            }
            prev = wifi[i];
        }
        return maxV;
    }
    
    while(start + 1 < end) {
        mid = (start + end) / 2;
        
        if(check(mid)) start = mid;
        else end = mid;
    }
    
    return start;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    
    for(int i = 0; i < n; i++) {
        long long a;
        cin >> a;
        //if(maxDist < a) maxDist = a;
        wifi.push_back(a);
    }
    
    sort(wifi.begin(), wifi.end());
    
    cout << binarySearch();
}

 

end값 제대로 넣어줌

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

using namespace std;

long long n, m;
//long long maxDist = 0;

vector<long long> wifi;

bool check(long long mid) {
    long long prev = wifi[0];
    long long cnt = 1;
    
    for(long long i = 1; i < n; i++) {
        long long cur = wifi[i];
        if(cur - prev >= mid) {
            prev = cur;
            cnt++;
        }
    }
    
    if(cnt >= m) return true;
    else return false;
}

long long binarySearch() {
    long long start = 0;
    long long end = 1000000001;
    long long mid;
    
    if(end - start == 1) return 1;
    if(n == m) {
        int prev = wifi[0];
        int maxV = 0;
        for(int i = 1; i < n; i++) {
            if(wifi[i] - prev > maxV) {
                maxV = wifi[i] - prev;
            }
            prev = wifi[i];
        }
        return maxV;
    }
    
    while(start + 1 < end) {
        mid = (start + end) / 2;
        
        if(check(mid)) start = mid;
        else end = mid;
    }
    
    return start;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    
    for(int i = 0; i < n; i++) {
        long long a;
        cin >> a;
        //if(maxDist < a) maxDist = a;
        wifi.push_back(a);
    }
    
    sort(wifi.begin(), wifi.end());
    
    cout << binarySearch();
}

 

---

3. Feedback

이분탐색을 거의 이해한 줄 알았는데 범위설정하는 법도 조금 더 알아봐야겠다..

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐