[Algo] 공유기설치 c++ // 매개변수 탐색 hard

* 의사코드

• 행동영역
  • f(x) 정의시 최대, 최소를 쓰지마라. 우리는 이문제를 결정문제로 바꿔서 풀어야한다.
  • 간격을 고정하고 탐색하라. (x)로 고정.
  • 되는지를 구현하는게 사실 핵심이다. (go 함수)
  • 참인경우, st = mid 임에 주의 // en = mid 아님!

st = mid / en = mid-1

f(x) : 두 공유기 사이의 거리가 x 일때, 되는지

• go 함수 구현
  • 완탐하면서 간격 <= 차이(cur, next)   ->   설치(cur갱신) , cnt+1
  • 설치된 공유기 갯수가 c 보다 큰지 return

//설치간격이 x 일때, 공유기 c개 이상 설치 가능한지
ll go(ll x) {
    ll cur = arr[0]; //현재 설치된 위치
    ll cnt = 1; //공유기 설치갯수, 1st는 항상설치
    for (int i = 1; i < n; ++i) {
        if (x <= abs(cur - arr[i])) { //이상이면 설치하면됨 (2 ,4) 에서 간격이 1인경우 4에 설치가능
            cur = arr[i];
            cnt++;
        }
    }

    return cnt >= c;
}

• f(x) 정의, go 함수 구현 모두 빡센 문제였다.
• f(x)를 현재간격으로 "고정" 하고
• 간격이 x일때 설치되는 공유기 수를 세고
• 그 값이 c 개 이상인지 확인.

 

* 전체코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int n, c;
ll arr[200000+4];
ll ret; //배정된 예산중 최대값

//설치간격이 x 일때, 공유기 c개 이상 설치 가능한지
ll go(ll x) {
    ll cur = arr[0]; //현재 설치된 위치
    ll cnt = 1; //공유기 설치갯수, 1st는 항상설치
    for (int i = 1; i < n; ++i) {
        if (x <= abs(cur - arr[i])) { //이상이면 설치하면됨 (2 ,4) 에서 간격이 1인경우 4에 설치가능
            cur = arr[i];
            cnt++;
        }
    }

    return cnt >= c;
}
int main()
{
    cin >> n>>c;
    for (int i = 0; i < n; ++i) {
        cin >> arr[i];
    }

    sort(arr, arr + n);
    ll st = 1; // 최소간격
    ll en = arr[n - 1] - arr[0]; //최대간격

    //f(x) : 설치간격이 x일때, 되는지
    while (st < en) {
        ll mid = (st + en+1) / 2;
        //cout << st << " "<< mid<<" " << en << "\n";

        if (go(mid)) {
            st = mid;
        }
        else {
            en = mid - 1;
        }
    }

    cout << st;

    return 0;
}