결정 알고리즘

n개의 마구간이 있고 c마리의 말이 있을 때 c마리의 말들을 가능한 멀리 떨어지도록 배치한다. 이때 가장 가까운 두 말 사이의 최대 거리를 구해보자.

 

마구간이 수직선상에 있고 현재 사용 가능한 마구간이 1번, 2번, 4번, 8번, 9번 마구간이라면

lt=1

rt=9

로 잡고 결정 알고리즘을 적용해보자.

 

mid=5 이면 가장 가까운 두 말의 거리가 5라는 뜻으로 3마리의 말을 배치하고자 하면

첫 번째 말이 1번 마구간,

두 번째 말이 2번, 4번 마구간에 들어가지 못하고 8번 마구간에 배치될 것이다.

세 번째 말은 9번 마구간에 들어가지 못하기 때문에

가장 가까운 두 말의 거리가 5라고 했을 때 마구간에 말을 2마리 밖에 넣지 못한다. -> 답이 될 수 없음 -> rt를 줄인다.

 

............처음엔 말을 먼저 배치하고 각각 거리를 구한 다음 가장 가까운 거리를 구해야 한다고 생각했었다.......

말이 세마리라면 100마리라면 20만마리라면???? 아찔했는데

결론은 결정 알고리즘을 통해서 말들의 가장 가까운 거리를 먼저 제시하고,

이 거리 이상으로 말들을 배치할 수 있냐를 검증해보는 것이었다............... 

 

def Count(len):
    cnt=1	# 첫번째 말을 배치
    ep=Line[0]
    for i in range(1, n):
        if Line[i]-ep>=len:	# 두 말 사이의 거리가 len보다 크다면 말을 배치할 수 있겠다
            cnt+=1 		# cnt 1 증가
            ep=Line[i]		# End Point 변경
    return cnt

 

Count(len) 함수는 주어진 거리(len)을 기준으로 말을 최대 몇 마리(cnt) 배치할 수 있는지 계산하는 함수이다.

 

첫 번째 마구간에는 무조건 말을 배치하고

이후 각 마구간을 돌면서 이전 말과의 거리 >= len 이면 말을 배치한다.

 

 

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

 

lt(최소 거리)와 rt(최대 거리)를 두고 이분 탐색을 수행하자.

mid 거리를 기준으로 Count(mid) 함수를 호출하여 말의 배치 가능 여부를 확인한다. 만약 Count(mid) >= c이면 c마리의 말을 배치할 수 있다는 의미로 res에 mid 값을 저장한다. 그리고 최적의 값을 구하기 위해 더 큰 거리를 탐색한다. (두 말 사이의 거리가 더 커져도 c마리의 말을 배치할 수 있는지) -> lt=mid+1

c마리의 말을 배치할 수 없다면 rt=mid-1로 두 말 사이의 거리를 줄인다.

 

while문을 lt<=rt일 때까지 진행하면 가장 가까운 두 말 사이의 최대 거리를 구할 수 있다.