[파이썬 알고리즘 문제풀이] - Section4 / 이분탐색(결정알고리즘) & 그리디 알고리즘 - 4

🎈 마구간 정하기(결정알고리즘)

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

▣ 입력설명
첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다.
둘째 줄부터 N개의 줄에 걸쳐 마구간의 좌표 xi(0<=xi<=1,000,000,000)가 한 줄에 하나씩
주어집니다.

▣ 출력설명
첫 줄에 가장 가까운 두 말의 최대 거리를 출력하세요.

▣ 입력예제 1
5 3
1
2
8
4
9

▣ 출력예제 1
3

import sys
# sys.stdin = open("input.text", "rt")


N, C = map(int, input().split())
data = []
for i in range(N):
    data.append(int(input()))

data.sort()

start = 1 
end = max(data)

def max_length(len):
    cnt = 1 #len일 때 놓을 수 있는 말의 개수 (시작부터 놓을거니까)
    now = data[0] #말 현재 위치
    for i in range(1, N):
        if data[i] - now >= len:
            cnt += 1
            now = data[i]
    
    return cnt

res = -242424242424
while start <= end:
    mid = (start + end) // 2 #가장 가까운 두 말 사이의 최대 거리 즉 모든 말들은 이 값보다는 같거나 켜야해 
    if max_length(mid) >= C:
        res = mid  #mid보다도 더 큰 값으로도 C를 만들 수 있을 수도 있으니. 이렇게 최대거리를 구하는거야.
        start = mid + 1
    else:   #C보다 작게 배치할 수 밖에 없다는건 최대거리를 mid로 하면 값의 유효한 범위를 넘어가.
        #답이 안되는 경우라면 인접한 두 말의 길이가 너무 길어서 원하는 마리 수를 다 배치 못하는거야
        end = mid - 1
print(res)

🎃 코멘트
아직 답이 될 수 있는 범위를 정한 이후에 조건을 어떻게 줘야 하는지 제대로 감을 못잡음. 문제를 잘 생각해서 범위를 주고 조건을 통해 어떻게 해야할지 고민하자.

일단 가까운 두 말 사이의 거리가 짧아질수록 말을 더 많이 배치할 수 있잖아.
거리가 짧아지면 개수가 많아져. 어쩃든 이 거리도 최대가 아니더라도 가까운 두 말 사이의 거리의 최댓값이 될 수는 있다는 생각 할 수 있어야 했음.