백준 2110(공유기 설치) - Python(파이썬) - 이분탐색

2110번: 공유기 설치

예제 설명

최소 거리는 1 , 최대 거리는 9(arr[-1])-1(arr[0]) = 8 

1) 최소 거리가 4인 경우(mid) 공유기 설치

집과 집 사이의 거리
start			mid =(1+8)//2=4				end
1	2	3	4	5	6	7	8

공유기 설치
1	2	4	8	9

최소 거리가 4가 되는 경우에는 1부터 시작해서 1+4=5 이상의 좌표에 공유기를 설치해야한다. 그렇기 때문에 1에 설치 후에 5이상의 좌표인 8에 설치를 한다. 그렇게 되면 총 공유기 설치는 2개가 되므로 공유기의 개수 3이랑 맞지 않게 된다. 따라서 최소 거리는 4보다  작아져야한다. 

=> end = mid-1 =3 

 

2) 최소 거리가 2인 경우(mid) 공유기 설치

집과 집 사이의 거리
start	mid =(1+3)//2=2	end
1	2	3	4	5	6	7	8

공유기 설치
1	2	4	8	9

최소 거리가 2가 되는 경우에는 1에 설치-> 1+2 = 3이상의 좌표인 4에 설치 -> 4+3 = 7 이상의 좌표인 8에 설치 

그렇게 되면 총 공유기 설치는 3개가 되므로 공유기의 개수 3이랑 동일하다. 공유기 사이의 거리를 가능한 크게 하여 설치하여야 하므로 한번 더 이분탐색으로 실행

=> start = mid+1

 

3) 최소 거리가 3인 경우(mid) 공유기 설치

start =3, end=3 => mid = (3+3)//2 = 3

집과 집 사이의 거리
		start, mid,end
1	2	3	4	5	6	7	8

공유기 설치
1	2	4	8	9

최소거리가 3인 되는 경우에는 1에 설치 -> 1+3 =4이상의 좌표인 4에 설치 -> 4+3 = 7이상의 좌표인 7에 설치

그렇게 되면 총 공유기 설치는 3개가 되므로 공유기의 개수 3이랑 동일하다. 

=> start = 3+1 = 4를 넣으면 end =3보다 크게 되므로 그만둔다.

 

문제 풀이

① 거리의 최솟값 start에 넣기, 거리의 최댓값 end에 넣기 
② 이분탐색을 통해 집과 집사이의 거리를 구한다.
-> 인접한 공유기 사이의 거리의 최솟값을 출력해야하므로 이분탐색을 할 때마다 공유기 사이의 거리의 최솟값을 구한다.
③ 공유기 개수가 c와 일치하는 경우에는 두 공유기 사이의 거리를 가능한 크게 하여 설치하라고 하였으므로 max의 값이 나오도록 한다.

💻Python(파이썬)

import sys
n,c = map(int,sys.stdin.readline().split())
house=[int(sys.stdin.readline()) for _ in range(n)]
#오름차순 정렬
house.sort()
#거리의 최솟값
start = 1
#거리의 최댓값(가장 맨 뒤에 값에서 가장 맨 앞에 값 뺴기)
end = house[-1]-house[0]
result =0
while start<=end:
    mid = (start+end)//2#2로 나누어서 소수점 버림
    now = house[0]
    count = 1
    #공유기 사이의 거리 두 간격의 거리
    tmp = end
    for i in range(1,n):
    	#현재 위치 + 거리의 값이상의 좌표에 공유기 설치
        if now + mid<=house[i]:
            tmp = min(tmp,house[i]-now)
            count+=1
            now = house[i]

    if count<c:#더 많이 설치 해야한다.-> 간격이 짧아져야함
        end =mid-1
    if count>=c:#설치가 완료되거나 더 많이 설치된 경우 -> 간격이 넓어져야함
        #공유기 사이의 간격은 가능한 크게 하여 설치하여야하므로 간격 비교
        start = mid+1
        result = max(result,tmp)

print(result)

💻Java(파이썬)

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int N = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        int[] house = new int[N];
        for(int i=0;i<N;i++){
            house[i]=Integer.parseInt(br.readLine());
        }
        Arrays.sort(house);
        int start = 1;
        int end = house[house.length-1]-house[0];
        int result =0;
        while(start<=end){
            int mid =(start+end)/2;
            int now = house[0];
            int count =1;
            //공유기 사이의 거리 두 간격의 거리
            int tmp = end;
            for(int i=1;i<N;i++){
                if(now+mid<=house[i]){
                    tmp = Math.min(tmp,house[i]-now);
                    count++;
                    now = house[i];
                }
            }
            if(count<C){
                end = mid-1;
            }
            if(count>=C){
                start = mid+1;
                result = Math.max(result,tmp);
            }
        }
        System.out.println(result);
    }
}