백준 2110번 공유기 설치

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

이분 탐색을 이용하여 풀어야하는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 주어진 집들의 좌표는 정렬되어있지 않으므로 정렬을 합니다.

2. 최소 거리는 1, 최대 거리는 처음 집과 마지막 집 사이의 거리입니다.

3. 이분 탐색을 진행하는데 해당 간격으로 공유기를 설치할 때 조건을 충족하는지 확인합니다.

4. 3번에서 조건을 충족하는 거리 중 최대를 출력합니다.

#include <iostream>

#include <algorithm>

using namespace std;

 

const int MAX = 200000;

 

int N, C;

int house[MAX];

 

bool possible(int dist)

{

        int cnt = 1;

        int prev = house[0];

        //조건 충족하는지 확인

        for(int i=1; i<N; i++)

                 if (house[i] - prev >= dist)

                 {

                         cnt++;

                         prev = house[i];

                 }

       

        //조건 충족

        if (cnt >= C)

                 return true;

        return false;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> C;

 

        for (int i = 0; i < N; i++)

                 cin >> house[i];

 

        sort(house, house + N);

 

        //최소거리, 최대 거리

        int low = 1, high = house[N - 1] - house[0];

        int result = 0;

        while (low <= high)

        {

                 int mid = (low + high) / 2;

                 if (possible(mid))

                 {

                         result = max(result, mid);

                         low = mid + 1;

                 }

                 else

                         high = mid - 1;

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~