[백준 2110][파이썬] 공유기 설치

https://www.acmicpc.net/status?user_id=sungmin123&problem_id=2110&from_mine=1 

채점 현황

이진 탐색으로 푸는 문제이다.

 

먼저 좌표를 정렬한다.

 

거리의 최솟값(low)은 1이고 거리의 최댓값(high)은 첫 번째 집부터 마지막 집까지의 거리이다.

 

두 값이 인자로 들어오면 그 중간값(mid)을 구하고 중간값이 조건에 부합하는지 확인한다.

 

부합한다면 첫 번째 인자로 mid+1, 두 번째 인자로 high를 넣어주고 다시 한 번 이진 탐색을 수행한다.

 

low>high가 되는 순간 멈춘다.

 

이 문제에서 조금 까다로운 부분이 중간값이 조건에 부합하는지 확인하는 방법이다.

 

가장 인접한 두 공유기 사이의 거리가 중간값보다 크거나 같아야한다.

 

    mid=(low+high)//2
    prev=li[0]
    cnt=1
    for i in li:
        if i-prev>=mid:
            cnt+=1
            prev=i
    if cnt>=c:
        res=max(res, mid)
        binary(mid+1, high)

 

이를 확인하기 위해서는 공유기가 위치한 가장 가까운 거리와 현재 나의 위치를 구하면 된다.

 

만약 공유기가 위치한 가장 가까운 거리( prev )와 현재 나의 위치( i )가 중간값보다 크거나 같다면

if i-prev>=mid:

공유기의 개수를 늘리고 공유기가 위치한 가장 가까운 거리를 현재 위치로 업데이트한다.

prev=i

 

만약 공유기가 위치한 가장 가까운 거리( prev )와 현재 나의 위치( i )가 중간값보다 작다면 공유기의 가장 가까운 위치는 업데이트되지 않는다.

 

위 그림에서 A, B 사이의 거리가 중간값보다 작고 A와 C 사이의 거리가 중간값보다 크다고 가정하자.

 

단순히 A와 B만 비교할 때는 중간값보다 작으므로 조건에 해당하지 않는다고 판단해서는 안된다.

 

중간값보다 작을 때 공유기의 가장 가까운 위치를 업데이트하지 않고 A와 C를 비교해야 올바르게 구할 수 있다.

 

이렇게 끝까지 반복문으로 돌면서 마지막으로 나온 cnt와 공유기의 개수를 비교해야한다.

 

<최종 코드>

import sys
input=sys.stdin.readline
n, c = map(int, input().split())
li=[]
for _ in range(n):
    li.append(int(input()))
li.sort()
res=0
def binary(low, high):
    if low>high:
        return
    global c
    global res
    mid=(low+high)//2
    prev=li[0]
    cnt=1
    for i in li:
        if i-prev>=mid:
            cnt+=1
            prev=i
    if cnt>=c:
        res=max(res, mid)
        binary(mid+1, high)
    else:
        binary(low, mid-1)
binary(1, li[-1]-li[0])
print(res)