[Python] 마구간 정하기

---

문제

 인프런 저작권 문제

 

 

코드

n,m = map(int,input().split())
Line=[]

def Count(len):
    cnt = 1
    endpoint = Line[0]
    for i in range(1, n):
        if Line[i]-endpoint >= len:
            cnt +=1
            endpoint = Line[i]
    return cnt

for _ in range(n):
    tmp=int(input())
    Line.append(tmp)

Line.sort()
rt = Line[n-1]
lt=1

while lt<=rt:
    mid = (lt+rt)//2
    if Count(mid) >= m: #배치 할 수 있는 마리 수
        res=mid
        lt=mid+1
    else:
        rt=mid-1

print(res)

 

접근법

 

이분 탐색으로 접근해서 가장 좋은 수를 찾는 방법이다

 

 

 

배운 점

이분 탐식 시 lt에 마냥 +1 을 더하는 것 보다 가운데 값을 가져와서 +1을 하는 것이 더 효율적인 방법이다