[백준] 2110번: 공유기 설치 풀이 및 해설(C++)

 

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

2110번: 공유기 설치

 

C++로 작성한 백준 문제 2110번 공유기 설치에 대한 문제 풀이다.

골드 4 문제로 이분탐색과 매개변수 탐색이 문제를 푸는데 필요한 주요 지식이다.

 

 

---

문제 설명

문제

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

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

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

 

입력

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

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

 

---

문제 파악하기

1. 집의 좌표들이 무작위로 주어지니 일단 집들의 좌표를 정렬하는게 문제를 풀기 좋을 것이다.
2. 공유기 사이의 거리가 최대라는 건, 가능한 공유기 끼리 서로 멀리 떨어져야 한다는 것이다.
3. 주어진 공유기의 개수가 아닌 공유기의 끼리의 최대거리를 미리 설정하고, 계산을 해보자

 

 

---

 

코드 및 설명

#include <iostream>
#include <algorithm>
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;

int main(){
    fastio;
    long long n,c,min,max,mid,data,saved;
    cin>>n>>c;
    long long arr[n];
    for(int i=0; i<n; i++){
        cin>>arr[i];
    }
    sort(arr,arr+n);
    max=arr[n-1]-arr[0];
    min=arr[1]-arr[0];
    for(int i=1; i<n-1;i++){
        if(arr[i+1]-arr[i]<min){
            min=arr[i+1]-arr[i];
        }
    }
    while(min<=max){
        mid=(min+max)/2;
        data=0;
        saved=0;
        for(int i=0; i<n-1; i++){
            data+=(arr[i+1]-arr[i]);
            if(data>=mid){
                data=0;
                saved++;
            }    
        }
        if(saved>=c-1){
            min=mid+1;
            
        }
        else{
            max=mid-1;
        }
    }
    mid=(min+max)/2;
    cout<<mid;

}

 

문제 풀이 쓰기

 

---

 

헤매었던 부분

오래 고민해보았지만 어떻게 풀어야 할지 전혀 가닥이 잡히지 않아 다른 블로그 분들의 도움을 많이 받았다. 이진탐색 키워드를 알고 있어도 여기서 이분탐색을 어떻게 쓰지? 싶었다.

 

https://st-lab.tistory.com/277

[백준] 2110번 : 공유기 설치 - JAVA [자바]

 

그래서 풀이를 찾다가 해당 블로그의 설명에서 큰 도움을 얻었다.

핵심은 일단 첫 집에 설치하고, 거리를 정하고, 해당 개수만큼 도출되는지 확인하는 것이다.

즉, 개수를 정해놓고 구하는게 아니라 거리를 정해놓고 개수를 구해야 한다.

 

 

내가 이 문제에서 가장 헷갈렸던 부분은 

 

1. 만약에 거리를 정해놓았다 치자.

2. 그리고 다음 공유기가 해당 거리를 만족해서 설치할 수 있는 환경이다.

3. 그럼에도 이번에 설치 안 하는 게 도움 될 때가 있지 않나? 하는 의문이었다.

 

그런데 결국 공유기 사이의 거리는 직전 공유기의 위치에만 상관이 있다.

 

 

---

설치할 수 있으면 무조건 하는 게 이득이다. 그리디 알고리즘처럼.  내가 헷갈렸던 부분을 직접 예시를 들려고 하니 막상 나오지 않았다. 항상 머릿속 의심스러운 반례는 직접 그려보자. 풀이를 어렵게 만드는 스스로 만들어낸 환상일 수 있다.

 

 

마무리

이진탐색 문제이지만 이진탐색 자체보다는 문제의 접근 방식이 더 중요한 문제였다.

1. 정해진 것과 그에 따라 바꿀 것, 즉 상수로 둘것과 변수로 둘 것을 바꿀 때 문제를 새로 볼 수 있고,

2. 의심스러운 반례는 스스로 만들어 낸 공포일 수 있다는 걸 깨달았다.