[2110번] 공유기 설치

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 이분 탐색, 이진 탐색

2. 투 포인터

이 문제는 binary search로 해결할 수 있는 문제이다.

우선 그렇게 될 수 있는 이유에 대해 생각해보자.

n제한이 20만이고 가능한 모든 경우의 수를 검사하기 위해서는 부르트 포스를 이용하면 O(n^2)이 걸리게 된다.

따라서 이 문제를 nlgn으로 구성해야 우리는 제한시간내에 풀 수 있게 되는데

그 방법을 bsearch로 생각해 볼 수 있다.

bsearch의 대상을 생각해보자.

공유기 길이의 최대를 구해야하기에 start를 1로, end를 공유기 최대 길이가 될 수 있는 값으로 둔다면

우리는 이진 탐색을 이용하여 mid를 계속해서 찍어가며 최대 길이를 알아 낼 수 있게 된다.

그리고 해당하는 mid를 이용하여 각 집마다 공유기를 모두 설치 할 수 있는지 확인하는 방법은 투포인터를 이용하여 고안해냈다.

더 많은 내용은 주석을 통해 달아두었다.

소스 코드 : 

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 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

#include <iostream> #include <cstdio> #include <algorithm> #include <vector>   using namespace std;   vector<int> arr; int n, m;   int binarySearch(int start, int end) {     int mid = (start + end) / 2;     int cnt = 0;     int ans = 0;       while (start <= end)     {         cnt = m;             mid = (start + end) / 2;           // 첫번째 집에는 무조건 공유기 설치한다 가정         cnt--;         int a = 0, b = 1; // 투 포인터 이용           while(b < n)         {             // 현재 b위치 집과 a위치 집이 최대 거리인 mid보다 크거나 같으면             // 공유기 설치하고 a위치를 b위치로 설정             if (arr[b] - arr[a] >= mid)             {                 cnt--;                 a = b;             }               b++;         }           // 공유기가 모두 설치 될 수 있다면         if (cnt <= 0)         {             start = mid + 1;             ans = max(ans, mid); // 최대 거리를 갱신해준다.         }         else             end = mid - 1;     }       return ans; } int main() {     scanf("%d %d", &n, &m);       int end = 0;     for (int i = 0; i < n; i++)     {         int val;         scanf("%d", &val);         arr.push_back(val);     }       // 이분 탐색을 위해 정렬     sort(arr.begin(), arr.end());       // 공유기 최대 거리가 될 수 있는 max값 지정      end = arr[n-1] - arr[0];       printf("%d", binarySearch(1, end));       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus