백준 2110번 문제. 공유기 설치

백준 2110번 문제. 공유기 설치

[Point] 파라메트릭 서치를 이용 (최적해 -> 이진탐색 + 결정)

공유기를 최대한 널찍널찍하게 설치할 수 있는 <최적의> 최대 거리를 찾는 문제다. 

이진탐색의 응용 버전인 파라메트릭 서치를 이용하면 된다.

간단한 개념은 이 게시글에 정리해두었으니 참조

알고리즘 자체는 어렵지 않다.

"음..좋아 너로 정했다!"

"문제 조건 만족!"

"헐..니가 만족된다구..? 좋아 일단 널 임시 정답으로 생각해둔 다음... 가라 다음 후보!"

"피카피카! 문제조건 만족!"

"헐 너도 만족되는구나! 가라 다음 후보!" 

이렇게 이진탐색으로 범위를 좁혀가면서 최적해를 구하면 된다.(무슨 소리인지는 나만 이해할 수 있을 것 같다......)

 

기본 뼈대는 다음과 같다.

1. 필요한 값을 입력받고, 집의 위치를 오름차순으로 나란히 정렬한다 ( 1 3 2 4 5 -> 1 2 3 4 5)

2. 정답이 될 수 있는 거리의 후보군을 생각해보자. 1이 가능한 최소 거리(left)일 것이고, pos[N-1] - pos[0]이 가능한 최대 거리(right)일 것이다.

우리는 이 [left, right] 의 범위 내에서 이진탐색으로 이후보 저 후보 꼽아보면서(gap), 우리가 구하고자하는 최적의 거리(ans)를 찾아내면 된다 

3. 일단 정답의 후보로 gap을 계산한다. 편의상 변수 이름을 gap이라고 지었지만 사실상 mid나 다름없다. 

4. gap을 정답이라 '가정하고' 문제 조건을 만족하는지 살펴본다. cnt는 임시 정답 후보(gap)로 시뮬레이션해봤을때 설치되는 공유기의 갯수를 의미하며, 기본적으로 맨 왼쪽 집에는 하나 설치하고 시작하기 때문에 1로 초기화한다.

5-1. 만약 우리의 임시 후보 gap이 문제 조건을 만족한다면... (인접한 설치 장소 간의 최소 거리를 찾는 문제이니  ">=" gap에서 헷갈리지 말자) 

일단 정답 변수인 ans에 저장해둔다. 그리고 혹시 존재할지도 모를 최적해가 있을 수 있으니, 후보 검증을 더 해보자. 어느 파트에서 후보를 골라야할까? 그렇다. 바로 gap의 오른쪽 파트, 그러니까, 현재 gap의 숫자보다 더 큰 숫자들이 존재하고 있는 [gap+1,Right] 부분을 보면 된다. 여기서 또 문제조건을 만족하는 후보를 만나면 그 친구가 ans에 덮어씌여지겠지

5-2. 만약 우리의 임시 후보 gap이 문제 조건을 만족하지 못한다면....

다시 말해 gap의 간격만큼 공유기를 설치해봤더니 실제 설치해야하는 공유기 수보다 적게 설치해버렸을 때, 우리는 간격을 더 좁혀서 오밀조밀하게 공유기를 설치해야할 의무가 있다. 어느 파트에서 후보를 골라야할까? 그렇다. gap보다 작은 숫자들이 존재하고 있는 [Left, gap-1] 부분에서 우리의 정답 후보를 찾아 떠나면 된다.

6. 5-1과 5-2의 과정을 반복하다보면 최적해가 ans에 저장된다. 출력하고 끝.

#include <stdio.h>
#include <stdlib.h>
 
int compare(const void* a,const void* b){
    int* aa=(int*)a;
    int* bb=(int*)b;
    return *aa-*bb;
}
 
int main(){
    int N,C,left,right,gap,i,std,ans;
    int pos[200000];
    int cnt=1;
 
    scanf("%d%d",&N,&C);
 
    for(i=0;i<N;i++){
        scanf("%d",&pos[i]);
    }
 
    qsort(pos,N,sizeof(int),compare);
 
    left=1;//가능한 최소 거리
    right=pos[N-1]-pos[0];//가능한 최대 거리
 
    while(left<=right){
        gap=(left+right)/2;
        cnt=1;
        std=pos[0];
 
        for(i=1;i<N;i++){
            if(pos[i]-std>=gap){
                cnt++;
                std=pos[i];
            }
        }
 
        if(cnt>=C){//실제 설치해야할 공유기 수 보다 더 많이 설치 -> 간격 늘여야
            ans=gap;
            left=gap+1; //오른쪽 파트에서 찾아보자
        }
        else{
            right=gap-1;//왼쪽 파트에서 찾아보자
        }
    }
    printf("%d\n",ans);
    return 0;
}