0911_이진탐색 공유기설치

백준 2110번 - 공유기 설치

이진탐색이란?

이진탐색은 술게임으로 유명한 업앤다운과 비슷한 개념이다. 병뚜껑 뒤에 써있는 숫자를 맞추는 게임인데, 범위의 중간값을 말해서 정답 범위를 줄여 나간다. 예를들어 1부터 100까지의 숫자 사이에서 랜덤으로 정해진 숫자 하나를 맞춰야 한다면 처음엔 50, 업이라면 50이하의 숫자는 탐색할 필요가 없으니 다음 탐색 부분은 75로 설정하는 등 절반씩 쪼개가며 탐색할 부분을 좁혀나가는 방법이다.

백준 2110

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

문제에서 주어진대로 N개 집에 C개의 공유기를 설치한다. 가장 인접한 공유기 사이의 거리가 최대가 되도록 해야한다.

이것을 순차적으로 찾는 방법도 있지만 비효율적이다. 이러한 탐색문제를 가장 빠르게 푸는 방법은 바로 이진탐색이다.

이 문제의 해결방법

1. 입력받은 집의 arr를 sort해서 정렬하기.
2. 이진탐색에서는 start, end 설정값이 중요하다. start는 1, end는 sort된 집의 arr의 처음값과 마지막 의 차이로 설정한다. 공유기를 만약 2개를 설치할 경우 집 arr의 처음과 마지막 의 차이가 공유기 설치 간격이 된다.
3. 공유기 간격을 가장 넓게 하려면 가장 처음 집에는 설치해야한다.
4. 설치를 다 끝냈는데 설치한 공유기 갯수가 C개가 넘어가면 더 넓게 설치할수 있다는 이야기이므로 설치거리를 mid+1로 설정해서 다시 앞집부터 설치
5. C개를 넘어가지 않는다면 더 촘촘히 공유기를 설치해야 된다는 이야기이므로 mid -1 로 설정

위 과정을 반복 실행하면 정답을 얻을 수 있다.

import sys
input = sys.stdin.readline
N, C =  map(int,input().split()) # 5 3
house = list(int(input().rstrip()) for _ in range(N));
print(house)
house.sort(); #[1,2,4,8,9]

start, end = 1, house[N-1] - house[0]; # 1, 8
result = 0;

if(C==2): # 집이 두개라면, 무조건 처음집과 마지막집 사이의 거리
    print(house[N-1] - house[0]);
else:
    while( start < end ):
        mid = ( start + end ) // 2; # 최소거리 + 최대거리 / 2 = 공유기설치 간격의 초기값
        count = 1; # 순회를 하면서 공유기 설치를 count 해야하므로 1로 초기화 해줘야 함.
        ts = house[0]; #공유기는 처음 집에 무조건 설치해야함 초기값 설정
        for i in range(N):
            if house[i] - ts >=mid:
                count+=1 #공유기설치
                ts = house[i] #마지막으로 공유기설치한곳 업데이트
        if count >= C: #공유기의 간격 좁히기
            result = mid
            start = mid +1
        elif count < C:
            end = mid
    print(result)

#  /**
            # *  [ 효율성 ]
            # *  - 메모리: 38984KB
            # *  - 시간 : 504ms
        #    */

총평 : 공유기 설치를 위한 간격 순회를 위한 값 = mid 로 설정해놓는 것과, while문 탈출 조건을 생각해내기가 어려웠다. 그리고 공유기를 맨 처음값에 무조건 설치를 해야 간격이 최대가 된다라는 설정을 생각해내기가 어려웠다. 탐색하고자 하는 범위를 start, end 로 설정하고, 찾아야 되는 값 = mid 그리고 언제까지 탐색을 할것인가? 탐색을 다 완료후에 결과값이 내가 원하는 값이냐의 여부에 따라 start, end 값 조율해주기.