[Algorithm] 마구간 정하기 (결정알고리즘)

N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ......, xN의 좌표를 가지며, 마구간간에 좌표가 중복되는 일은 없습니다. 현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다.
각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다. C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요.

<내 답안>

def Count(length):
    cnt = 1
    p = 0
    for i in range(1, n):
        if li[i] - li[p] >= length:
            cnt += 1
            p = i
    return cnt


n, c = map(int, input().split())
li = []
res = 0
for _ in range(n):
    li.append(int(input()))
li.sort()

lt = 1
rt = max(li)
while lt <= rt:
    mid = (lt+rt)//2
    if Count(mid) >= c:
        res = mid
        lt = mid + 1
    else:
        rt = mid - 1

print(res)

문제 읽었을 때 이해가 되지 않아 해설 앞부분을 듣고 풀었다.
Count(mid)로 리턴된 값은 말의 수 이다.
c보다 크거나 같다면 당연히 c마리의 말을 넣을 수 있다. (만약 c보다 작다면 그것은 최대로 넣을 수 있는 말의 수라는 것이니 c마리를 넣을 수 없다.)
따라서 이분탐색에서 범위를 mid 위로 다시 정하면 된다.
Count 함수 내에서는 첫번째 마구간에 말 한 마리를 넣어두고 시작하는 것으로 하여 인덱스 0, 즉 p = 0를 가지고 풀었다.

<모범답안>

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

n, c = map(int, input().split())
Line = []
for _ in range(n):
    tmp = int(input())
    Line.append(tmp)
Line.sort()
lt = 1
rt = Line[n-1]
while lt <= rt:
    mid = (lt+rt)//2
    if Count(mid)>=c:
        res = mid
        lt = mid + 1
    else:
        rt = mid - 1
print(res)