[백준] 2110번 공유기 설치 - python 파이썬 (이분탐색)

문제

 

 

 

 

사실 이 문제는 어떤 알고리즘을 써야 할지 전혀 감히 잡히지 않았던 문제였다.

 

구글링을 통해 이분탐색을 써야 된다는 걸 알게 됐지만 그래서 target이 뭔데....? 라는 생각만 들고 감이 안잡혔었다.

 

target이 명시적으로 딱 주어지지 않더라도 이것을 뽑아내는 능력을 좀 길러야 할 것 같다.

 

 

이분 탐색을 활용해 풀어보자면, 목표는 C개를 설치할 때의 간격(mid)의 최댓값을 찾는 것이다.

공유기 개수를 조정하면서 mid 값을 점점 키워가며 탐색한다.

탐색 과정에서 C개를 설치할 수 있으면 mid를 더 키워도 되는지 확인하기 위해 start = mid + 1을 진행한다.

반대로 C개를 설치할 수 없으면 간격이 너무 크다는 뜻이므로 end = mid - 1을 줄인다.

이 과정을 start <= end 동안 반복하며 최댓값을 갱신하므로, 마지막으로 저장된 mid가 C개를 설치할 수 있는 간격 중 최댓값이 된다.

 

 

 

 

정답코드

 

n, c = map(int, input().split())
homes = [int(input()) for _ in range(n)]
homes.sort()


start = 1
end = homes[-1] - homes[0]
ans = 0

while(start <= end):
    mid = (start + end) // 2
    now = homes[0]
    count = 1

    for i in range(1,len(homes)):
        #현재 구한 간격보다 크거나 같은 위치에 있는 집만 세면 현재 간격으로 몇개의 공유기를 설치할 수 있는 알 수 있음
        if homes[i] >= now + mid:
            count += 1
            now = homes[i]
    
    if count >= c:
        start = mid + 1
        ans = mid
    else:
        end = mid -1

print(ans)

 

 

 

 

이 문제의 가장 Key Point는 이 문제를 이분탐색으로 풀어야겠다는 생각과 이분탐색을 쓸 때 target을 어떤걸로 할 지를 생각해서 구현해내는 것이다.