[Algorithms] 결정&그리디 알고리즘-마구간 정하기(결정 알고리즘)

 

 

 

• 가장 가까운 두 말의 거리가 최대가 되게 = 말 사이의 최소 거리가 크면 클수록 좋다
• 이분 탐색에서 mid의 값이 커지면 커질 수록 좋다는 의미 
• 찾은 최대 거리에서 말이 C 마리 이상이여도 답이 된다 **** 
• 첫 번째 말이 첫 번째 x좌표에 있다고 가정하고 cnt=1 부터 하고 시작한다  

 

import sys
 
# sys.stdin = open("input", "rt")
house, horse = map(int, input().split())
distance = [int(input()) for _ in range(house)]
distance.sort()
 
def count(mid):
    cnt=1                                       # 첫 번째 말이 첫 번째 좌표에 이미 배치되어 있다고 가정하고 시작
    dis_origin = distance[0]                    # 첫 번째 좌표
    for i in range(1, house):
        if distance[i] - dis_origin >= mid:     # 두 좌표의 거리 값이 mid length 보다 크거나 같으면
            cnt+=1                              # 말을 배치하고
            dis_origin=distance[i]              # 그 좌표부터 다시 거리 쟤기 시작
    return cnt
 
 
left=1                                          # 거리의 최소값은 1이다 (z좌표 값이 중복되지 않는다고 하였으므로)
right=max(distance)                             # 거리는 어찌되었든 가장 큰 x좌표 값 이하여야 한다
res=0
while(left <= right):
    mid=(left+right)//2
 
    if count(mid) >= horse:                     # 말이 지정된 수보다 많이 카운팅되도 지정된 수는 어쨋든 배치 가능하다는 소리이므로
        res=mid
        left=mid+1
    else:
        right=mid-1
 
print(res)