[python] 백준 2110 :: 공유기 설치 (이분 탐색)

[공유기 설치]

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

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

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

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

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

풀이

전체 코드

import sys

N, C = map(int, input().split())
houses = [int(sys.stdin.readline()) for _ in range(N)]
houses.sort()

left, right = 1, houses[-1] - houses[0] # 최소 거리, 최대 거리
result = 0
while left <= right:
    mid = (left + right) // 2  # 중간 지점

    prev_house = houses[0]  # 이전 공유기가 설치된 집
    count = 1  # 설치한 공유기의 개수

    # 모든 집을 순회하면서 mid 거리 이상인 경우에만 공유기를 설치
    for i in range(1, len(houses)):
        if houses[i] - prev_house >= mid:
            prev_house = houses[i]
            count += 1

    # 공유기를 C개 이상 설치할 수 있는 경우, mid 값을 저장하고 더 큰 값으로 이동
    if count >= C:
        result = mid
        left = mid + 1
    # 공유기를 C개 이상 설치할 수 없는 경우, 더 작은 값으로 이동
    else:
        right = mid - 1

print(result)

 

0. 풀이 방법

• 이진 탐색을 활용한다.
• 각 집 간의 최소 거리와 최대 거리의 합을 구해서 그 중간값 이상의 거리에 떨어진 집에 공유기를 설치해본다.
• 설치한 공유기의 수의 개수에 따라서 중간값을 조정해가며 반복한다.

 

1. 오름차순으로 정렬

houses.sort()

• 이진탐색을 하기 위해 오름차순으로 정렬한다.
  (이진탐색을 할 때는 오름차순 정렬이 더 편함 👍🏻)

 

2. 이진탐색을 위한 최초값 설정

left, right = 1, houses[-1] - houses[0] # 최소 거리, 최대 거리

• 최소 거리(left): 1
• 최대 거리(right): 좌표가 제일 큰 집 - 좌표가 제일 작은 집

 

3. 공유기를 깔아보자

• 우선 맨 처음 집에 설치한다고 가정하고 시작한다.

    prev_house = houses[0]  # 이전 공유기가 설치된 집
    count = 1  # 설치한 공유기의 개수

 

• 설치한 집과 거리가 mid 이상인 집을 발견하면, 그 집에도 공유기를 설치한다.
• 공유기가 설치된 직전 집의 값을 저장하는 prev_house의 값을 지금 설치한 집으로 바꿔준다.
• 공유기를 하나 설치했으니까 count 값도 +1

    # 모든 집을 순회하면서 mid 거리 이상인 경우에만 공유기를 설치
    for i in range(1, len(houses)):
        if houses[i] - prev_house >= mid:
            prev_house = houses[i]
            count += 1

 

4. 현재 경우에서 설치된 공유기의 수를 문제에서 제시한 공유기 수와 비교한다.

• 공유기의 개수가 딱 맞게 깔렸거나 너무 많이 깔렸으면 공유기 간의 거리를 늘려준다.
  그럼 더 적은 집에 깔리겠지!
• 딱 맞게 깔린 경우와 너무 많이 깔린 경우를 묶은 이유
  👉🏻 딱 맞게 깔린 경우, 거리를 더 늘릴 수 있으면 좋으니까!
• 그리고 이게 답이 될 수 있으니까 result에 담아둔다.
  (탐색 끝나면, 즉 while문 끝나면 result를 출력할 거임)

    # 공유기를 C개 이상 설치할 수 있는 경우, mid 값을 저장하고 더 큰 값으로 이동
    if count >= C:
        result = mid
        left = mid + 1

 

• 공유기가 적게 깔렸으면, 공유기 간의 거리를 좁혀준다.
  그럼 더 많은 집에 깔리겠지!

    # 공유기를 C개 이상 설치할 수 없는 경우, 더 작은 값으로 이동
    else:
        right = mid - 1

 

 

끝~!