백준 2110번 공유기 설치

문제링크

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

사용 알고리즘

  º  이분탐색

 

시간복잡도

  º  $\mathcal{O}(Nlog(10^{10}))$

 

풀이

 

문제에서의 설명이 애매하게 느껴지는데 공유기를 설치한다는 의미는 연속하는 점들을 묶어주는 것과 같은 의미라고 보면 됩니다. 즉, 그룹을 만들어주는 것인데 그룹간의 간격의 최대길이를 지정해 놓고 그 간격으로 최대한의 그룹을 만들어서 묶어주면 그룹이 C개 이상이면 문제를 해결할 수 있습니다.

 

최대길이를 시작점과 끝점의 거리차로 해서 이분탐색을 시작하여 매 탐색시 그룹간격 최대길이로 그룹을 만들어주는 로직을 해줍니다.

그 로직은 전 점의 좌표와 현 점의 좌표의 거리차를 그룹간격 최대길이를 mid라 할때 mid 이상인지 검사해줍니다. mid미만의 값이면 한 공유기에 넣어도 최대길이를 초과할 일이 없기 같은 공유기에 넣어주고, 아니면 새 그룹으로 시작해줍니다.

따라서 탐색은 최대로 나올 수 있는 좌표 10억과 1의 차이인 $\mathcal{O}(log(10^{10}))$=10

매 탐색시 $\mathcal{O}(N)$의 시간소모. 최종적으로 둘을 곱해줍니다.

 

소스코드

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() {     ios_base::sync_with_stdio(false);     cin.tie(NULL), cout.tie(NULL);     int n,c;     vector <long long> v;     cin >> n >> c;     v.resize(n);     for (int i = 0; i < n; i++)         cin >> v[i];     sort(v.begin(), v.end());     int prev,result,ans=0,mid, left = 1, right = v[n - 1]-v[0]; // 오른쪽 최대범위 시작점과 끝점의 거리차     while (left <= right)     {         mid = (left + right) / 2;         result = 1;         prev = v[0];         for (int i = 1; i < n; i++)         {             if (v[i] - prev >= mid) // 현재 설정한 최대거리 이상이면 공유기를 하나더추가해줌             {                 result += 1;                 prev = v[i];             }         }         if (result >= c) // 공유기 개수가 C이상이면 정답보다 큰지 비교         {             left = mid + 1;             if (mid > ans)                 ans = mid;         }         else             right = mid - 1;     }     cout << ans;     return 0; } Colored by Color Scripter

cs