[백준] 2110번 : 공유기 설치

문제

 

---

풀이

 

myunji.tistory.com/264?category=1154147

[백준] 1654번 : 랜선 자르기

이 문제와 풀이가 같다.

 

굳이 다른 점을 찾자면 저 문제는 특정 길이에 대해 자를 수 있는 랜선의 수를 리턴한다면 이건 특정 거리에 대해 설치 가능 여부를 리턴 받는다는 점..? 이렇게 말하면 뭐가 다른 건지 감이 안올테니 바로 코드로 넘어가겠다.

---

소스코드

 

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

using namespace std;

typedef long long ll;

int N, C;
vector<ll> house;

bool isInstall(ll dist) { //이 거리로 설치할 수 있는지 확인
    int cnt = 1;
    ll pos = house[0];

    for (int i = 1; i < house.size(); i++) {
        if ((house[i] - pos) >= dist) {
            cnt++;
            pos = house[i];
        }
        if (cnt == C)
            return true;
    }
    return false;
}

ll upperSearch(ll left, ll right) {
    while (left <= right) {
        ll mid = (left + right) / 2;
        if (!isInstall(mid))
            right = mid - 1;
        else if(isInstall(mid)) //else로 처리할 수 있지만 lower랑 비교하기 위해 유지
            left = mid + 1;
    }
    return right;
}

int main() {
    ll input;

    cin >> N >> C;
    for (int i = 0; i < N; i++) {
        cin >> input;
        house.push_back(input);
    }
    sort(house.begin(), house.end());

    cout << upperSearch(1, house[house.size() - 1]);
}

1654번과 다른 부분은 isIntall 함수 뿐이다.

 

bool isInstall(ll dist) { //이 거리로 설치할 수 있는지 확인
    int cnt = 1;
    ll pos = house[0];

    for (int i = 1; i < house.size(); i++) {
        if ((house[i] - pos) >= dist) {
            cnt++;
            pos = house[i];
        }
        if (cnt == C)
            return true;
    }
    return false;
}

isInstall 함수에서는 입력받은 거리의 간격으로 공유기를 설치할 수 있는지 확인한다.

집들을 미리 좌표순으로 오름차순 정렬했으니 첫번째 집에 공유기를 설치하고 2번째 집부터 비교해 나가면서 공유기를 설치한다.

만약 C개 만큼의 공유기를 설치하는 데 성공했다면 true를 반환하지만 그렇지 않다면 false이다.

 

false값이 나왔다는 것은 이 거리보다 좁게 공유기를 설치해야 한다는 것이다.