백준 2110번 공유기 설치

정보

문제 바로가기 [클릭]

난이도: Gold5

관련 개념: #이분탐색 #매개변수 탐색

---

조건

시간 제한	메모리 제한
2 초	128 MB

---

문제

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

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

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

---

입력

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

---

출력

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

---

예제 입출력 1

입력

5 3
1
2
8
4
9

출력

3

---

코드(파이썬)

import sys


def check(l):
    now = routers[0]
    result = False
    cnt = 0

    if n == 2:
        result = True
    else:
        for r in routers[1:]:
            if r - now >= l:
                now = r
                cnt += 1
                
            if cnt == m-1:
                result = True
                break
        
    return result

n, m = map(int, sys.stdin.readline().split())
routers = sorted([int(sys.stdin.readline()) for _ in range(n)])

nearest_max = min(routers[-1]-routers[0], ((routers[-1] + routers[0]) // (m-1))) + 1
nearest_min = 1

while nearest_min + 1 < nearest_max:
    mid = (nearest_max + nearest_min) // 2
    
    if check(mid):
        nearest_min = mid
    else:
        nearest_max = mid
    
print(nearest_min)

---

특이사항

• 해결방법
  • 유니온-파인드를 통해 도시들을 트리로 구분지음
  • 출발지와 도착지의 트리 루트가 다르다면 다른 트리에 속하므로 도달할 수 없음
• 내 코드(40,132KB, 412ms)에 비해 우수한 코드(바로가기, 40,132KB, 316ms)와 비교

  • import sys
    
    def binary_search(house, n, start, end):
        if start > end:
            return end
            
        mid = (start + end) // 2
    
        result = 1
        len = house[0]
        for i in house:
            if len + mid <= i:
                len = i
                result += 1
    
        if result >= n:
            return binary_search(house, n, mid+1, end)
        else:
            return binary_search(house, n, start, mid-1)
    
    
    
    input = sys.stdin.readline
    
    n, k = list(map(int, input().split()))
    house = sorted([int(input()) for i in range(n)])
    
    start, end = 1, house[-1] - house[0]
    
    print(binary_search(house, k, start, end))
    
    

  • 전체 로직은 유사함
  • 모든 라우터를 확인하는 반복문만 차이가 나므로 해당 부분에서 차이가 발생하는 것으로 추정됨

---

참고문헌

-