백준 g4 2110 공유기 설치 c++

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

2110번: 공유기 설치

 

문제

집의 좌표 x가 N개 주어지고 설치해야하는 공유기 개수 C가 주어진다.

이때 가장 인접한 공유기 간의 거리의 최댓값은?

 

풀이

처음에는 가장 인접한 공유기 간의 거리의 최댓값은 중간의 중간의 중간의 ... 로 차례대로 놓는 게 아닐까 생각했는데

ex.

1 10

1 5 10

1 5 7 10

이런 식으로

 

근데 1 5 7 10보단 3등분해서 1 4 7 10이 더 최적의 값이다. 결국 답지를 봤음

 

parametric search인 것 같다 아마도

가장 최댓값(최적화 문제) -> 공유기 설치 간격을 x로 두었을 때 c개를 설치할 수 있는지(결정 문제)

설치할 가장 적절한 공유기 간격을 이분탐색으로 풀면 된다

 

수도 코드

// 공유기 간격을 이분탐색으로 구하기

while st < en
	res = solve(mid)
    
    if res < C // 공유기 개수가 부족하므로 간격 줄이기
    	en = mid-1
    else if res == C || res > C // 최댓값을 구해야하므로 간격 더 늘려보기
    	st = mid


// 공유기 간격 interval이 주어질 때 설치되는 공유기 개수를 구하는 solve()

int solve(int interval)
	idx = 0
    cnt = 0
    
    while idx < N
    	cnt++ // 시작 공유기 포함
        idx = lower_bound(idx ~ N까지, arr[idx]+interval찾기) - arr

 

 

전체 코드

/*boj g4 2110 공유기 설치*/
#include <algorithm>
#include <iostream>
#define MAXN 200005
using namespace std;

int N, C;
int arr[MAXN];

int solve(int interval) {
    int idx = 0;
    int cnt = 0;

    while (idx < N) {
        cnt++;
        int nextIdx = lower_bound(arr + idx, arr + N, arr[idx] + interval) - arr;
        idx = nextIdx;
    }
    return cnt;
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> C;

    for (int i = 0; i < N; i++)
        cin >> arr[i];

    sort(arr, arr + N);

    int st = 1;
    int en = 1000000000;

    while (st < en) {
        int mid = (st + en + 1) / 2;

        int res = solve(mid);

        if (res < C)
            en = mid - 1;
        else
            st = mid;
    }

    cout << st << "\n";
}

 

---

참고

https://wooono.tistory.com/404

https://github.com/encrypted-def/basic-algo-lecture/blob/master/0x13/solutions/2110.cpp