백준 2110 - 공유기 설치

문제 설명

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 집이 주어지고 C개의 공유기를 설치해야 한다.

C개를 최대한 넓은 간격으로 설치할 때, 최대 간격을 구하는 것이다.

 

집의 좌표의 범위가 1,000,000,000로 굉장히 크고 간격을 알고 있을 때, 공유기를 설치할 수 있는지 여부를 N만에 판단할 수 있기 때문에 패매트릭 서치로 문제를 해결할 수 있다.

우선, 공유기 최대 간격은 가장 앞집과 뒷집의 간격일 것이다.하지만, 집이 0부터 시작할 수  있기 때문에 예외가 발생한다.예를 들어, 집이 [0, 1]로 주어졌다고 가정해 보자.그럼 최대 간격은 1이 되야 한다.하지만, $ (1+0) / 2 = 0$이 된다.따라서, 초기에 설정하는 최대 간격에 1을 더해 예외 없는 초기값을 설정해야 한다.또한, 최솟값은 집은 겹쳐서 존재할 수 없기 때문에  무조건 1이 된다.

for (int i = 0; i < N; i++)
{
    cin >> house[i];
}

sort(house.begin(), house.end());
long long right = house.back() - house[0] + 1;
long long left = 1;

 

그럼 간격을 알고있을 때, 설치 가능 여부를 판단하는 방법을 알아보자.

우선, 목적은 최대 간격으로 설치하는 것이기 때문에 가장 처음시작은 제일 왼쪽(앞) 집이어야 한다.

반대의 상황을 가정해 보면 이해가 쉬울 것이다.

만약, 가장 앞집이 아니라 한 칸 오른쪽부터 시작하면 C개를 모두 설치하지 못하는 경우가 생길 것이다.

2부터 공유기를 설치한다면 다음 집은 4는 간격(3)보다 앞에 있기 때문에 설치가 불가능하다.

그다음으로 설치 가능한 집은 8이기 때문에 총 2개밖에 설치하지 못한다.

하지만, 1부터 시작한다면 [1, 4, 8(9)]에 설치하여 총 3개를 설치할 수 있다.

이는 현재 예시뿐만 아니라 모든 경우에 적용된다.

따라서, 가장 앞집부터 설치하며 간격(K) 이후에 나타나는 집을 세주면 최대 몇 개를 설치할 수 있는지 알 수 있다.

설치 개수가 C개 이상일 경우 K간격으로 설치가 가능하다는 뜻이다.

bool canPossible(long long gap)
{
    //C개 설치 가능? gap간격
    long long target = house[0] + gap;
    long long cnt = 1;
    for (int i = 1; i < N; i++)
    {
        if (house[i] >= target)
        {
            cnt++;
            target = house[i] + gap;
        }
    }

    return C <= cnt;
}

 

이제 최소 간격과 최대 간격을 이진 탐색을 통해 줄여가며 C개의 공유기를 설치가능한 최대 간격을 구하면 된다.

long long ans = 0;
while (left <= right)
{
    long long mid = (right + left) / 2;
    if (canPossible(mid))
    {
        left = mid + 1;
        ans = max(ans, mid);
    }
    else right = mid - 1;
}

 

또 한 가지 주의할 점은, 좌표가 상당히 크기 때문에 int가 아닌 long long을 사용해주어야 한다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int N, C;
vector<long long> house;

bool canPossible(long long gap)
{
    //C개 설치 가능? mid간격
    long long target = house[0] + gap;
    long long cnt = 1;
    for (int i = 1; i < N; i++)
    {
        if (house[i] >= target)
        {
            cnt++;
            target = house[i] + gap;
        }
    }

    return C <= cnt;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> C;

    house.resize(N);
    for (int i = 0; i < N; i++)
    {
        cin >> house[i];
    }

    sort(house.begin(), house.end());
    long long right = house.back() - house[0] + 1;
    long long left = 1;

    long long ans = 0;
    while (left <= right)
    {
        long long mid = (right + left) / 2;
        if (canPossible(mid))
        {
            left = mid + 1;
            ans = max(ans, mid);
        }
        else right = mid - 1;
    }

    cout << ans;

    return 0;
}

---