Beakjoon 2110 공유기 설치

07 Feb 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/2110

나의 풀이

이 문제는 이진 탐색을 이용하여 풀 수 있다.

1. 먼저 각각의 집의 좌표를 오름차순으로 정렬한다.
2. 두 공유기 사이의 거리는 1이상 x_n - x_1이하의 범위를 갖게 되고 이 범위안에 가장 인접한 두 공유기 사이의 최대 거리를 기준으로 이진 탐색을 한다.
3. 가장 인접한 두 공유기 사이의 최대 거리를 mid라고 할 때 설치할 수 있는 공유기의 최대 수를 구한다.
4. 3번에서 구한 공유기의 수가 C보다 작다면 공유기의 숫자가 부족하기 때문에 거리를 좁혀 공유기의 개수를 늘려야 한다. -> end = mid - 1
5. 3번에서 구한 공유기의 수가 C 이상이라면 공유기의 숫자가 많기 때문에 그만큼 여유가 있다고 판단하여 가장 인접한 두 공유기 사이의 최대 거리를 높여 start = mid + 1로 한다. 이 조건을 만족하는 경우가 정답일 수 있기 때문에 조건을 만족하면 임시정답으로 설정해둔다.

풀이 코드 : 2110 공유기 설치

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int N, C, num;
    cin>>N>>C;
    vector<int> arr;
    for(int i=0;i<N;i++){
        cin>>num;
        arr.push_back(num);
    }
    
    sort(arr.begin(), arr.end());

    int start = 1;
    int end = arr.back() - arr[0];
    int answer = 0;
    while(start<=end){
        int mid = (start + end)/2;
        int c = 1;
        int last = arr[0];
        for(int i=1;i<N;i++){
            if(mid <= arr[i] - last){
                last = arr[i];
                c++;
            }
        }   

        if(c >= C){
            start = mid + 1;
            answer = mid;
        }
        else{
            end = mid - 1;
        }
    }
    cout<<answer;
}

채점결과