[이코테] 이분탐색 - 공유기 설치 with 파이썬

1. 문제

• 백준 2110 문제와 동일
  • 링크
• 집 n개가 수직선 위, 각각 다른 좌표
• 공유기 c개를 설치 하고자 한다.
• 한 집에 공유기 하나 설치, 인접한 두 공유기 사이의 거리를 가능한 크게
• c개의 공유기를 n개의 집에 적당히 설치, 가장 인접한 두 공유기 사이의 거리를 최대로

입출력 조건 및 예

2. 아이디어

• 최적화 대상은 집간의 간격
  • 최소값은 1, 최대값은 첫집과 끝집의 거리
• mid가 들어간 목적함수
  • 첫집에 무조건 설치 후 다음 집부터 mid 간격이상으로 설치 했을 때, c개 설치 가능한가
  • 다음 집부터 끝집까지 mid간격 이상으로 설치
    • for 문, house[i] >= dist(지금까지 거리) + mid
• 판단
  • count 가 c보다 크거나 같으면, mid는 넓어져야 하고, 답이 될 수 있다.
  • count 가 c보다 작으면, mid는 좁혀져야하고, 답이 될 수 없다.

3. 예제 코드

# 입력 
n, c = map(int, input().split())

houses = [int(input()) for _ in range(n)]  # 집 좌표 입력 
houses.sort()  # 이분탐색을 위한 정렬 

# 이분탐색
# 초기값 설정 (최적화 대상은 집의 간격)
start = 1 
end = houses[-1] - houses[0]

result = 0  # 결과 값 초기화 

# 이분탐색 시작
while start <= end :
    mid = (start + end) //2 
    
    dist = houses[0]  # 지금까지 거리 , 첫집 설치 
    count = 1
    
    for i in range(1, n):  
        if houses[i] >= dist + mid:    # 설치할 집 위치 >= 지금까지의 거리 + 간격 
            count += 1
            dist = houses[i]           # 설치할 집의 위치가 지금까지의 거리로 갱신
            
    if count >= c : 
        start = mid + 1 
        result = mid 
    else : 
        end = mid - 1 

print(result)

4. 배운점

• 목적함수 포함 이분탐색 리마인드

참조

• 이것이 취업을 위한 코딩테스트다. with 파이썬