(백준 2110번 공유기 설치 C++) 라이님 블로그 대회 알고리즘 따라잡기 6) 이분탐색 3

이분탐색,,, 디버깅 포기한 문제가 속출 중인지라 오늘은 시작부터ㅋㅋㅋㅋ다른 분들의 풀이를 탐독하는 시간을 가져보았다. 안 그래도 자존감 떨어지데 백준까지 나를 힘들게 하면 너무 슬프니까 오늘은 많은 멋진 분들의 코드를 참고했다.

 

백준 2110번

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

2110번: 공유기 설치

 

이 문제의 아이디어는 이분탐색의 대상을 무엇으로 할지이다.

 

위치를 기준으로 하면 어렵다. 

 

예를 들어

7개의 집(1, 2, 3, 4, 5, 6, 7)에 3개의 와이파이를 놓기 위해서는

1 2 3 4 5 6 7 → 거리는3이고, x= 1, 4, 7에 와이파이를 놓으면 되지만

 

7개의 집(1, 2, 3, 4, 5, 6, 7)에 4개의 와이파이를 놓기 위해서는

1 2 3 4 5 6 7 → 거리는2이고, x= 1, 3, 5, 7에 와이파이를 놓아야 한다.

 

C의 갯수와 와이파이를 설치해야 하는 집의 위치는 연관이 없으므로, 이런 접근은 잘못된 접근이다.

 

그래서 아래 풀이들은 X = 와이파이의 최대 거리(문제에서 구하고자 하는 값)을 변수로 놓았다.

와이파이가 2개일 때는 가장 멀리 있는 2개의 집 거리를 반환하면 되고, 

와이파이가 3개 이상이면 MAX = 가장 멀리 있는 2개의 집 거리 / 2를 최대로 하여 1과 MAX 사이의 값을 갖는다.

 

이렇게 되면 우리가 아는 이분탐색을 사용할 수 있는데,,,,!!!!!!

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int N, C;
    scanf("%d %d", &N, &C);
    vector<int> House(N);
    for (int& h : House) scanf("%d", &h);

    sort(House.begin(), House.end());

    if (C == 2) {
        printf("%d", House[N - 1] - House[0]);
        return 0;
    }

    int lo = 1, hi = House[N - 1] - House[0];
    
    auto f = [&House, C](int mid) -> int {
        int cnt = 1, current = House[0];
        for (int h : House) {
            if (h - current >= mid) {
                cnt++;
                current = h;
            }
        }
        return cnt;
    };

    while (lo + 1 < hi) {
        int mid = (lo + hi) / 2;
        if (f(mid) >= C) lo = mid;
        else hi = mid;
    }
    printf("%d", lo);
    return 0;
}

 

이분탐색에서 가장 헷갈리는 부분은 lo와 hi의 관계이다.

 

lo와 hi의 설정은 라이님 블로그를 보면서 정했는데, 

while(lo+1 < hi)로 정하는 순간 lo +1 = hi, 즉 lo와 hi는 1차이가 나는 연속하는 수가 된다.

 

이렇게 되면 lo 또는 hi의 값을 mid로 업데이트할 때 lo를 업데이트 하는 부분에 등호가 들어가도록 업데이트하고

(지금 문제에서는 f(mid) >= C)) 답도 lo로 반환하면 된다. 

 

 

 

 

[참고]

1. 개인적으로 제일 이해가 잘 된 풀이

https://great-park.tistory.com/m/45

2. https://my-coding-notes.tistory.com/119

3.https://velog.io/@ngchaneok/%EB%B0%B1%EC%A4%80-2110%EB%B2%88-%EA%B3%B5%EC%9C%A0%EA%B8%B0-%EC%84%A4%EC%B9%98-C