백준 | 2110 - 공유기 설치 (python)

📶 공유기 설치

이진 탐색을 이용한 최대값을 찾는 문제이다.

 

 

---

✏️ 문제

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

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

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

 

입력

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

 

출력

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

 

 

---

💡 해결방법

이진 탐색을 이용해 간격을 비교하는 문제이다.

이진 탐색을 위해 입력받은 집의 위치를 정렬한다. (sort)

 

이진 탐색을 위해 start 값과 end 값을 지정해주어야 한다. 간격이 가장 좁을 때는 1일때 이고, 간격이 가장 넓을 때는 sort한 값에서 home[n-1]-1 이다. (home은 집의 위치가 저장된 배열, n은 집의 개수)

start = 간격이 가장 좁을 때 = 1

end = 간격이 가장 넓을 때 = home[n-1]-1

 

n = 집의 개수 = 5
c = 설치할 공유기의 개수 = 3
home = 집의 위치가 저장된 배열 = [1, 2, 8, 4, 9]

입력 값이 위와 같다고 가정할 때, start = 1, end = 9-1 = 8, mid = (start+end) // 2 = 4 이다.

 

집과 집 사이의 간격을 비교해가면서 간격이 4보다 크거나 같은것이 있는지 확인해나가면 된다. pre_home의 초기값은 home[0] 값이며 만약 mid 값보다 현재 위치 - 공유기를 설치한 이전 위치가 더 클때 공유기를 설치하면 된다. 이후 pre_home을 갱신해야 한다.

# 공유기 설치 - 간격 비교
    for i in range(1, n):
        if home[i]-pre_home >= mid:
            cnt += 1
            pre_home = home[i]

 

 

이때 변수로 cnt = 설치가 가능한 집의 개수를 사용해야 하는데, cnt의 초기값은 0이 아닌 1로 지정해야 한다. 왜냐하면 간격을 비교해나가는 것이기 때문에 간격 1개를 비교한다고 볼때 공유기는 집 2개에 설치가 되어야하는 것이기 때문이다.

 

만약 cnt의 값보다 c(설치해야 하는 공유기의 값)이 더 클 때는 공유기를 더 설치해야 한다. 공유기를 증가시켜야 하므로 간격을 좁혀야 한다. → end = mid-1

반대로 cnt의 값이 c보다 더 클때는 공유기의 개수를 감소시켜야 하므로 간격을 넓혀야 한다. → start = mid+1

 

이진 탐색을 이용해 위와 같은 과정을 반복하면 최종적인 mid값이 출력값이 된다.

 

 

👩🏻‍💻 소스코드

import sys

n, c = map(int, sys.stdin.readline().split())
home = [int(sys.stdin.readline()) for _ in range(n)]
home.sort()

start = 1
end = home[n-1]-home[0]

while start<=end:
    mid = (start+end) // 2
    cnt = 1
    pre_home = home[0]

    # 공유기 설치 - 간격 비교
    for i in range(1, n):
        if home[i]-pre_home >= mid:
            cnt += 1
            pre_home = home[i]

    # 설치해야하는 공유기의 개수가 작을 때 -> 간격 넓힘
    if cnt >= c:
        result = mid
        start = mid+1
    # 설치해야하는 공유기의 개수보다 클 때 -> 간격 좁힘
    else:
        end = mid-1

print(result)

---