[백준] 2110 공유기 설치(C++)

2110번: 공유기 설치 (acmicpc.net)

2110번: 공유기 설치

---

난이도 : 골드5

 

풀이방법:

이분탐색 문제인데,

내가 구한 방식은 일단 좌표를 오름차순으로 정렬을하고,

첫번째 인덱스부터 시작해서 반복문을 돌려 차이가 mid이상이면 두 점 차이가 가능하다는 의미에서 chk=true로 해주었고,

공유기 개수를 +1 해준다. 그다음 mid이상이나오는 인덱스부터 다시시작해서 다음번째 그다다다음번째가 mid이상인지 계속 체크해서 공유기 개수가 c가 될때 까지 계속해준다.

그래서 결국에 반복문을 빠져나왔을때 chk=false이면 불가능하다는 것이고

chk = true면 가능한 차이 라는 것이므로 mid값이 최대가 되는 지점이 ans가 되게 된다.

 

말로 설명하니까 쫌 복잡한데 

코드보면 이해가 갈듯!! 

 

코드 :

#include <iostream>
#include <algorithm> 
using namespace std;

int n, c, arr[200002], ans;
int main() {
    cin >> n >> c;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr, arr + n);
    int l = 0, r = arr[n - 1] - arr[0];
    while (l <= r) {
        int mid = (l + r) / 2;

        int cnt = 1, idx = 0;
        bool chk = false;
        for (int i = 0; i < n; i++) {
            if (cnt == c) break;
            for (int j = i; j < n; j++) {
                if (arr[j] - arr[i] >= mid) {
                    i = j-1; // i는 i++때문에 i+1인덱스부터 반복문을 시작하게된다
                    chk = true;
                    cnt++;
                    break;
                }
                else {
                    chk = false;
                }
            }
        }
        if (chk == true) {
            l = mid + 1;
            ans = mid;
        }
        else {
            r = mid - 1;
        }
    }
    cout << ans;   
}