[BOJ] 2110번: 공유기 설치 (파이썬)

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

2110번: 공유기 설치

---

- 두 공유기 사이의 거리는 첫 번째 집과 마지막 집 사이의 거리를 넘어갈 수 없기 때문에 end 를 첫 번째 집과 마지막 집 사이의 거리로 설정합니다.

 

- mid 를 두 집 사이의 거리로 설정합니다.

- 현재 집과 그다음 집 사이의 거리가 mid 보다 크거나 같다면, 공유기의 설치가 가능합니다.

    - 설치한 공유기의 개수 valid 를 1 증가시킵니다.

 

- 설치된 공유기의 개수 valid 가 설치해야 하는 공유기의 개수 c 보다 크거나 같아지는 경우,

    - 결과 result 에 mid 를 저장합니다.

    - start 에 mid + 1의 값을 저장합니다.(현재 집 사이의 거리 mid 가 더 커져도 원하는 공유기 개수만큼 설치할 수 있다는 것을 의미하기 때문에, mid 의 값을 크게 변경합니다.)

- 설치된 공유기의 개수 valid 가 설치해야 하는 공유기의 개수 c 보다 작은 경우,

    - 현재 집 사이의 거리 mid 로는 원하는 공유기 개수만큼 설치할 수 없기 때문에, mid 값을 감소시킵니다.

import sys

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

houses.sort()
start = 1
end = houses[-1] - houses[0]
result = 0

while start <= end:
    mid = (start + end) // 2
    left = houses[0]
    valid = 1
    for i in range(1, n):
        if houses[i] >= left + mid:
            valid += 1
            left = houses[i]

    if valid >= c:
        start = mid + 1
        result = mid
    else:
        end = mid - 1

print(result)

---

파이썬 기본 라이브러리에서 제공하는 이진 탐색 함수를 사용하면 다음과 같이 풀이할 수 있습니다.

import sys
from bisect import bisect_left

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

houses.sort()
start = 1
end = houses[-1] - houses[0]
result = 0

while start <= end:
    mid = (start + end) // 2
    left = 0
    valid = 0
    while left < n:
        valid += 1
        left = bisect_left(houses, houses[left] + mid)

    if valid >= c:
        start = mid + 1
        result = mid
    else:
        end = mid - 1

print(result)

파이썬 기본 라이브러리에서 제공하는 함수를 사용하면 같은 문제를 더 짧은 시간에 해결할 수 있습니다.

위: bisect 사용 / 아래: 직접 구현