[이분탐색(결정알고리즘)][그리디 알고리즘] - 마굿간 정하기(결정 알고리즘)

문제

주어진 n마리 만큼의 말이 주어진 거리에 존재한다고 할 때 최대의 거리에 c마리 만큼 놓을 수 있는 수를 찾아라

문제 풀이

def Count(mid):
    cnt = 1
    #무조건 첫 위치는 인덱스 0번부터 시작!
    end_point = Line[0]
    #0번 자리엔 이미 확인 했기 때문에 1~n까지
    for i in range(1, n):
        if Line[i] - end_point >= mid:
            cnt += 1
            end_point = Line[i]
    return cnt
        
n, c = map(int,input().split())
Line = [int(input()) for _ in range(n)]
Line.sort()

lt = 1
rt = Line[n-1]
res = 0
while lt <= rt:
    mid = (lt+rt) // 2
    #원하는 말 갯수보다 더 많은 말을 놓아도 정답으로 일단 인정
    if Count(mid) >= c:
        res = mid
        lt = mid + 1 
    else:
        rt = mid - 1

print(res)

• 최대를 찾을 땐 범위를 오른쪽으로 옮겨서 최소를 찾을 땐 범위를 왼쪽으로 옮겨서 찾는다.

• 대략 for 문이 이렇게 진행이 된다. 이때 cnt는 2를 리턴하고 이 값은 c보다 작기에 right에 있는 pointer를 왼쪽으로 옮겨 더 작은 mid를 이용해 최댓값을 찾는 진행을 한다.