[알고리즘 문제풀이] 공유기 설치

문제 제목 : 공유기 설치

문제 난이도 : 중

문제 유형 : 이진 탐색

https://www.acmicpc.net/problem/2110
시간 제한 : 2초
메모리 제한 : 128MB

문제풀이 아이디어

< 소스코드 >

import sys

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

def binary_search(array, start, end, target):
    global n
    
    while start <= end:
        mid = (start+end) // 2
        value = 0
        count = 1
        for i in range(n):
            if house[i] - house[value] >= mid:
                count += 1
                value = i
        if count < target:
            end = mid-1
        else:
            start = mid+1
    return (start+end)//2
        
def solution(house, c):
    mingap = 1
    maxgap = house[-1] - house[0]
    answer = binary_search(house, mingap, maxgap, c)
    return answer

print(solution(house, c))