[Baekjoon, Python] 2110번 : 공유기 설치

도입

백준 단계별 풀기에서 이분탐색 다섯 번째 문제이다.

백준 2110번 문제, 입력, 출력

---

백준 2110번 입출력 예제 1

---

풀이

0. router = 공유기.

   rtn = 답을 담을 변수. (return의 약자) 

   home_list = 집의 위치를 담는 리스트.

   count = count_r 선언 위치만 다를 뿐 나타내는 것은 같다. 

   var_T = 설치할 공유기 개수 (target)

 

1. mid값을 어떻게 산출하고 어떤 것을 계산하는데 쓰이는지를 설정하자. mid값을 정하기 위해서는 high값과 low값이 필요하다. 이 값은 N개의 집들이 들어있는 home_list에서 가장 큰값과 가장 작은 값으로 부터 거리의 최댓값 최솟값으로 한다. 따라서, high을 max, low를 min으로 네이밍하겠다. 중요한 것은 거리라는 것이다. 거리를 계산하는데 이분탐색을 사용하겠다는 것이고, 이 거리를 사용한 계산식을 통해 공유기의 개수를 count할 것이다. max는 list중 가장 큰 값-list중 가장 작은 값, min은 1로 한다. 

 

2. mid값을 계산해서 공유기 개수를 count한다. 어떻게 count할 것인가.  list들의 인덱스(x)를 하나씩 올려가면서 now_router와의 거리가 mid값(거리)보다 클 때 count++한다. (그때 x값의 집에 공유기를 놓겠다는 뜻) 그리고 now_router를 해당 x로 세팅한다.  

 

3. 이렇게 계산된 router(공유기) 개수가 target router 수와 비교를 한다. 

---

코드

from sys import stdin

def count_router(distance,home_list):       #router의 개수를 count하는 함수
    count = 1
    now_router = home_list[0]

    for x in range(1,var_H):                # key algorithm, 기준이 되는 now_router와 home[x]의 거리가 mid_d 보다 크거나 같다면 count++
        if (distance <= home_list[x] - now_router):
            count += 1
            now_router = home_list[x]
    
    return count

def binary_router(var_T,home_list):
   
    max_d, min_d = home_list[-1]-home_list[0], 1       # 최대 거리, 최소 거리(1)

    while min_d <= max_d :                 
        mid_h = (max_d + min_d)//2         # 중간 값
        count_r = count_router(mid_h,home_list)     # router 개수 count 함수의 매개변수로 mid_d,와 home_list를 넘김.
        
        if count_r < var_T:                         # Target router 개수를 못채운 경우
            max_d = mid_h - 1
        elif count_r >= var_T:                      # Target router 개수 채우거나 넘긴경우 (충족)
            min_d = mid_h + 1
            rtn = mid_h                             # 최종 결과값 저장

    return rtn

var_H, var_T = map(int,stdin.readline().split())
home_list = list(map(int,stdin.readlines()))
home_list.sort()

print(binary_router(var_T,home_list))

---

마무리

 이분탐색 다섯 번째 문제였는데, 생각보다 알고리즘적 고민이 필요했다. 한개의 공유기를 설치하고, 그것을 점차 mid값만큼 늘려간다는 것, 즉 count_router함수의 for문이 핵심이였다.