[BOJ] Q2110 공유기 설치

[BOJ] Q2110 공유기 설치

Question

Language: Python

Difficulty: Gold 5

우선 입력 조건을 보면 집의 좌표가 1~10억까지이므로 이를 순차적으로 탐색하게 되면 시간 초과가 발생하게 된다. –> 이분 탐색을 이용해서 풀이하라는 문제이다.

공유기를 총 3대 설치했을 때의, 공유기간 간격을 최대화하고 싶다는 의미이다.

그러면 공유기 간 간격에 대해 이분탐색을 진행하면 될 것 같다

공유기 간격을 1~(max_coordinate - min_coordinate)에 대해서 이분탐색을 진행하면서, 만약 공유기의 개수가 초과하게 되는 경우 간격을 넓히고, 공유기 개수가 부족한 경우 간격을 좁히는 식으로 이분탐색을 수행해본다.

Solution

def solution(coordinates, antennas):
    coordinates.sort()

    start=1
    end=coordinates[-1]-coordinates[0]
    result=0
    
    while start <= end:
        med=(start+end)//2
        count=1
        starting_point=coordinates[0]
        
        for i in range(1,len(coordinates)):
            if coordinates[i]>=starting_point+med:
                count+=1           
                starting_point=coordinates[i]
                
        if count>=antenna_num:
            start=med+1
            result=med
        else :
            end=med-1
    print(result)

if __name__ == "__main__":
    point_num, antenna_num=map(int,input().split())
    inputs=[]
    for _ in range(point_num):
        inputs.append(int(input()))
    solution(inputs,antenna_num)