백준 2110 공유기 설치 Python 3

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

2110번: 공유기 설치

 

최종 코드

• GitHub -> https://github.com/hwayeon351/BEAKJOON-Algorithms/blob/main/BJ2110.py

GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음

import sys

def find_router_loc(N, C, houses):
    left = 1
    right = houses[-1] - houses[0]
    while left <= right:
        mid = (left + right)//2
        cur = houses[0]
        cnt = 1
        for i in range(1, N):
            if cur + mid <= houses[i]:
                cur = houses[i]
                cnt += 1
        if cnt >= C:
            left = mid+1
            answer = mid
        else:
            right = mid-1
    return answer


input = sys.stdin.readline
N, C = map(int, input().split())
houses = list()
for _ in range(N):
    houses.append(int(input()))
houses.sort()
print(find_router_loc(N, C, houses))

---

풀이 과정

N개의 집 중 C군데에 공유기를 하나씩 설치하는 문제이다.

공유기를 설치할 때에는 가장 인접하게 설치된 공유기의 거리를 최대로 해야한다.

0 <= 집의 좌표 <= 1,000,000,000으로 O(log n)의 시간복잡도로 알고리즘을 짜지 않으면 시간초과를 예상할 수 있다.

따라서, 공유기와 공유기 사이의 거리를 기준으로 left와 right 탐색범위를 반으로 계속해서 줄여나가는 이분 탐색 알고리즘을 활용할 수 있다.

공유기 사이의 거리 mid 값을 기준으로 mid 거리 이상 떨어진 집에 공유기를 설치해나가면서 최적의 공유기 사이의 거리를 구해줘야 한다.

import sys

def find_router_loc(N, C, houses):
	#인접한 두 공유기 사이의 거리의 최솟 값은 1이고, 최댓값은 첫 집에서 끝 집 사이의 거리이다
    left = 1
    right = houses[-1] - houses[0]
    
    #이분 탐색 -> O(Nlogx)
    while left <= right:
    	#두 공유기 사이의 거리를 mid로 가정
        mid = (left + right)//2
        
        #mid 거리 이상 떨어진 집에 공유기 설치
        #현재 공유기가 설치된 위치 -> 첫 집부터 공유기를 설치해 나간다
        cur = houses[0]
        #설치된 공유기 개수 카운트
        cnt = 1
        for i in range(1, N):
        	#현재 위치에서 mid 거리 이상 떨어진 집에 공유기를 설치한다
            if cur + mid <= houses[i]:
                cur = houses[i]
                cnt += 1
                
        #mid 거리 이상을 두고 설치된 공유기 개수가 C보다 많거나 같은 경우,
        if cnt >= C:
        	#가능한 최대 거리를 찾기 위해 left 범위를 늘린다
            left = mid+1
            #mid 거리로 C개를 설치할 수 있으므로 answer 갱신
            answer = mid
            
        #mid 거리 이상을 두고 설치된 공유기 개수가 C보다 적은 경우,
        else:
        	#mid 값을 줄이기 위해 right 범위를 줄인다
            right = mid-1
    return answer

input = sys.stdin.readline
N, C = map(int, input().split())
houses = list()
for _ in range(N):
    houses.append(int(input()))
    
#집 좌표 오름차순 정렬 -> O(NlogN)
houses.sort()
print(find_router_loc(N, C, houses))

#시간복잡도 = O(log n), 공간복잡도 = O(n)