[BOJ] 공유기 설치 - 파이썬

March 11, 2021

문제

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

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

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

입력

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

출력

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

예제 입출력

내 코드

N, C = map(int, (input().split()))
house = [int(input()) for _ in range(N)]

def countRouter(distance):
    count = 1
    cur_house = house[0] #시작점
    for i in range(1, N): #집 순회
        if cur_house + distance <= house[i]: #이전 집에서 해당 거리보다 멀리 떨어진 집인지 체크
            count += 1
            cur_house = house[i]
    return count

house.sort()
start, end = 1, house[-1] - house[0]

while start <= end: #이진탐색
    mid = (start+end) // 2

    if countRouter(mid) >= C:
        answer = mid
        start = mid + 1
    else:
        end = mid - 1

print(answer)

전체적으로 기본적인 아이디어는 이진 탐색을 통해 푸는 건데, 또 공유기 개수와 갭을 고려해야 한다. 그래서 거리를 기준으로 설치될 수 있는 곳들을 찾으면 거리를 늘려주고, 만약 설치할 곳이 없다면 거리를 줄여 설치할 곳을 찾는다. 이렇식으로 반복하여, 최대 거리를 찾는다.

문제 풀이 아이디어

일단 좌표 값의 범위를 살펴보면 xi (0 ≤ xi ≤ 1,000,000,000)인데, 이렇게 큰 수가 나오는 순간 이진 탐색을 고려해봐야 한다. 이렇게 값이 크면, O(logN)의 알고리즘을 고려해봐야 한다.