[BOJ] 2110번 공유기 설치

#Binary Search #Gold4 #Python

 

문제 요약

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

도현이는 공유기 C개를 설치하려고 한다.

- 최대한 많은 곳에서 와이파이를 사용하려고 한다.

- 한 집에는 공유기를 하나만 설치할 수 있다.

- 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

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

 

<제한 조건>

- 집의 개수 N: (2 ≤ N ≤ 200,000)

- 공유기의 개수 C (2 ≤ C ≤ N)

- 집의 좌표: xi (0 ≤ xi ≤ 1,000,000,000)

 

문제 접근

구하려는 답은 (C-1)개의 공유기 사이의 거리 간격 중에서 값이 가장 작은 거리 간격 (= 가장 인접한 두 공유기 사이의 거리)의 최댓값이다.

처음 접근했을 때는 재귀 함수로 조합을 만들어서 조합별로 가장 작은 거리 간격을 구하고 그 중에서 max 값을 구해야 되겠다고 생각했다. 그런데 이 방법은 시간 초과가 나는 방법이었다.

시간 초과를 해결할 수 있는 좋은 방법은 이분 탐색이다. 

 

문제 풀이 (1) 재귀 함수 이용 - 시간 초과

import sys
input = sys.stdin.readline

def calculate_minimum(installed):
    minimum = float('inf')
    for i in range(1, len(installed)):
        gap = installed[i] - installed[i - 1]
        minimum = min(minimum, gap)
    return minimum

def generate_combinations(houses, depth, start, installed, max_distance):
    if depth == 0:
        max_distance[0] = max(max_distance[0], calculate_minimum(installed))
        return

    for i in range(start, len(houses)):
        installed.append(houses[i])
        generate_combinations(houses, depth - 1, i + 1, installed, max_distance)
        installed.pop()

def find_maximum_min_distance(houses, C):
    max_distance = [0]
    generate_combinations(houses, C, 0, [], max_distance)
    return max_distance[0]

if __name__ == '__main__':
    N, C = map(int, input().split())
    houses = sorted(int(input().strip()) for _ in range(N))
    print(find_maximum_min_distance(houses, C))

 

1. generate_combinations 함수를 통해 가능한 모든 조합을 생성한다.

   - visited 배열을 두는 대신 start 파라미터를 통해서도 조합을 생성할 수 있다.

      -> 조합에 넣을 요소를 선택할 때 기존에 선택한 요소의 인덱스보다 큰 인덱스를 가진 요소만 선택할 수 있도록 하는 장치이다.

2. depth == 0이 될 때 조합별 가장 인접한 거리 간격을 구한 후, 지금까지 구한 값 중에 최댓값을 계산해서 max_distance[0]에 저장한다.

     -> 배열을 이용하여 주소 참조를 통해 함수끼리 값을 공유할 수 있게 한다. max_distance = [0]

 

이런 식으로 조합을 만든다.

 

*itertools의 combination을 사용한 풀이

import sys
from itertools import combinations

input = sys.stdin.readline

def calculate_minimum(installed):
    minimum = float('inf')
    for i in range(1, len(installed)):
        gap = installed[i] - installed[i - 1]
        minimum = min(minimum, gap)
    return minimum

def find_maximum_min_distance(houses, C):
    max_distance = 0
    for installed in combinations(houses, C):
        max_distance = max(max_distance, calculate_minimum(installed))
    return max_distance

if __name__ == '__main__':
    N, C = map(int, input().split())
    houses = sorted(int(input().strip()) for _ in range(N))
    print(find_maximum_min_distance(houses, C))

 

문제 풀이 (2) 이분 탐색

import sys
input = sys.stdin.readline

def can_install(houses, min_distance):
    last_installed = houses[0]
    count = 1

    for i in range(1, len(houses)):
      if houses[i] - last_installed >= min_distance:
        last_installed = houses[i]
        count += 1
        if count >= C: return True
    return False

def find_max_min_distance(houses, C):
    left = 1
    right = houses[-1] - houses[0]
    result = 0

    while left <= right:
        mid = (left + right) // 2

        if can_install(houses, mid):
          result = mid
          left = mid + 1
        else:
          right = mid - 1
    return result

if __name__ == '__main__':
    N, C = map(int, input().split())
    houses = [int(input().strip()) for _ in range(N)]
    houses.sort()

    print(find_max_min_distance(houses, C))

 

1. 집 좌표들은 오름차순 정렬을 해준다. (그렇지 않으면 매번 간격을 구할 때마다 절댓값을 구해줘야 한다.)

2. 최소 간격은 1이고, 최대 간격은 (좌표값이 가장 큰 집의 좌표 - 좌표값이 가장 작은 집의 좌표, 공유기 2개를 설치할 경우)이다.

3. 가장 인접한 거리 간격을 이분 탐색한다. 이때, 최소 이 간격 이상으로 C개의 공유기를 설치할 수 있는지 can_install 함수에서 확인한다.

---

소감

재귀함수와 이분 탐색 둘 다 잘하고 싶다!