[C++] 백준 2110 - 공유기 설치(이분 탐색, 무식하게 풀기, brute force, binary search)

0. [c++] 백준

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

1. 풀이

처음에 이 문제에 이진 탐색을 적용하기 까다로워서 무식하게 모든 경우에 접근하는 방법으로 시도를 해보았다.

1. 무식하게 풀기(모든 경우 탐색)

현재 설치한 공유기의 수와 공유기를 설치한 위치를 변수에 담아 DFS방식으로 모든 위치에 배치를 하도록 해주었습니다.

공유기를 설치하며 현재 설치한 공유기의 거리중 가장 짧은 거리를 MIN이라는 전역변수에 저장해주었고, 모든 공유기를 설치한 이후, ret이라는 변수에 MIN의 값중 가장 큰 값이 저장되도록 해주었습니다.

2. 이진 탐색 적용

이런저런 생각을 해보았는데, 이진 탐색을 적용하기 좋은 데이터는 바로 거리 데이터라는 것이었습니다.

배치를 시작하기 전, 우선 어느 거리마다 공유기를 설치할 것인지 정의한 이후 배치를 시작하는 방향으로 진행해보았습니다.

알고리즘의 진행은 다음과 같습니다.

1) 함수를 오름차순으로 정렬

2) high에 arr[N-1](x좌표가 가장 큰 값)을 저장

3) low에 0을 저장

4) mid에는 high와 low의 중간값을 저장하며 mid의 크기를 넘어가는 구간마다 공유기를 설치

5) 설치한 공유기의 수가 C의 크기를 넘어가면 mid의 길이 중 최댓값을 ret에 저장하며 low = mid + 1

6) 넘지 못한 경우라면 high = mid - 1로 변경

7) 4~6과정 반복

8) 최종적으로 ret을 출력

2. 소스코드

1. 무식하게 풀기

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

#include<iostream> #include<algorithm>     using namespace std;   int N, C; int arr[200001]; int MIN = 1000000007; int ret = 0;   void calc(int num, int pos) {     if (num == C) {         if (ret < MIN)             ret = MIN;         return;     }     else {         for (int i = pos + 1; i < N;i++) {             int temp = MIN;             int dist = arr[i] - arr[pos];             if (dist < MIN)                 MIN = dist;             calc(num + 1, i);             MIN = temp;         }     } }   int main() {     cin.tie(0);     cin.sync_with_stdio(0);       cin >> N >> C;     for (int i = 0;i < N;i++) {         cin >> arr[i];     }          sort(arr, arr + N);       calc(1, 0);          cout << ret; } Colored by Color Scripter

cs

2. 이진 탐색 적용

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

#include<iostream> #include<algorithm>     using namespace std;   int N, C; int arr[200001]; int MIN = 1000000007; int ret = 0;   int main() {     cin.tie(0);     cin.sync_with_stdio(0);       cin >> N >> C;     for (int i = 0;i < N;i++) {         cin >> arr[i];     }          sort(arr, arr + N);       int high = arr[N - 1], low = 0, mid;     int pos, count;     while (low <= high) {         mid = (low + high) / 2;         pos = 0, count = 1;    //가장 첫번째 arr[0]에는 바로 설치하고 시작한다.         for (int i = 1;i < N;i++) {             if (arr[i] - arr[pos] >= mid) {                 pos = i;                 count++;             }         }         if (count >= C) {             if (ret < mid)                 ret = mid;             low = mid + 1;         }         else             high = mid - 1;     }          cout << ret; } Colored by Color Scripter

cs

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!