공부공간

BOJ - 2110 ) 공유기 설치 본문

알고리즘/이분탐색

BOJ - 2110 ) 공유기 설치

개발자가될수있을까? 2019. 12. 17. 12:29


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

 

2110번: 공유기 설치

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (1 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

www.acmicpc.net

서로다른 지점에 공유기를 설치하면서 가장 멀리 떨어지게 설치하는 거리를 구하는 문제이다.

 

첫번째에 놓았다면, FOR문을 돌면서 나머지와의 거리를 계산해주고 CNT로 그 값을 반환하여서 C와 비교하면서

 

거리값인 MID를 이분탐색으로 업데이트해준다.

 

처음에 LEFT 를 배열중 가장작은값으로 초기화 시켰는데 틀렸습니다가 나와서 

 

LEFT 를 0부터 증가시켰더니 통과 됐다.

 

여기서 MID는 거리를 의미하는데 LEFT를 배열의 가장작은 값으로 초기화시키면

 

그보다 작은 값에서 정답이 나올경우를 체크 못해주어서 그렇다.


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
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
int n, c;
vector< long long> num;
long long ans;
void input() {
    cin >> n >> c;
    for (int index = 0; index < n; index++) {
        long long t; cin >> t;
        num.push_back(t);
    }
 
}
 
long long count(long long mid) {
    long long cnt = 1;
    long long pos = num[0];
    for (int index = 0;  index < n; index++) {
        if (num[index] - pos >= mid) {
            cnt++;
            pos = num[index];
        }
    }
    return cnt;
}
void solution() {
 
    sort(num.begin(), num.end());
    
    long long left =  1;
    long long right = num[n - 1];
    long long mid;
 
    while (left <= right) {
 
        mid = (left + right) / 2;
 
        long long cnt = count(mid);
        if (cnt < c) {
            right = mid - 1;
        }
        else {
            ans = mid;
            left = mid + 1;
        }
    }
    cout << ans;
}
 
int main(void) {
 
    input();
    solution();
    return 0;
}
 

'알고리즘 > 이분탐색' 카테고리의 다른 글

BOJ - 8983 ) 사냥꾼  (0) 2020.10.01
BOJ - 2473 ) 세용액  (0) 2020.08.28
BOJ - 2805 ) 나무자르기  (0) 2019.12.17
BOJ - 2512 ) 예산  (0) 2019.12.16
Comments