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

문제

N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, x3, ..., xN의 좌표를 가지며, 마구간에 좌표가 중복되는 일은 없습니다. 

 

현수는 C마리의 말을 가지고 있는데, 이 말들은 서로 가까이 있는 것을 좋아하지 않습니다.

각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다.

C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력하는 프로그램을 작성하세요.

 

입력설명

첫 줄에 자연수 N(3<=N<=200,000)과 C(2<=C<=N)이 공백을 사이에 두고 주어집니다.

둘째 줄부터 N개의 줄에 걸쳐 마구간의 좌표 xi가 한 줄에 하나씩 주어집니다.

 

출력설명

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

 

입력예제 1

5 3

1

2

8

4

9

 

입력받아서 수직선 상에 정렬을 해야 함.

lt = 1 , rt = 9 

가장 가까운 두 말의 최대 거리는 1~9 사이의 거리일 것.

 

1+9/2 => 5가 되나 확인을 하는 것.

무조건 첫 번째 좌표에다가 말을 놓아야 함.

 

5일 때, 2, 4 둘 다 안됨 8 가능하니까 놓을 수 있음 , 넣을 수 있는 말이 2마리 밖에 넣지 못한다.

배치할 수 있는 말이 2마리 밖에 되지 않는 것.

 

 

출력예제 1

3

 

 

나의 답

def Count(mid):
    start = spot[0]
    cnt = 1 # 최소 첫번째 지점에 말을 놓음
    
    for i in spot:
        if (i-start)>mid:
            cnt+=1
            start=i
            
    return cnt

N, C = 5, 3

spot = [1,2,8,4,9]
spot = sorted(spot, reverse=False)

lt = spot[0]
rt = spot[-1]
res = 0

while lt<=rt:

    mid = (lt+rt)//2
    
    if C<=Count(mid):
        lt = mid+1
    else:
        rt = mid-1

    res = mid
    

print(res)

 

최소로 갈 수 있는 거리 : lt

최대로 갈 수 있는 거리 : rt

 

반씩 쪼개가면서 확인... count 하는 함수로 확인해준다... 범위가 좁혀지다보면 최대 거리를 구할 수 있다.

답이 될 수 있으면 res 는 무조건 바꿔가는 것이다.

 

강의 답안 답

def Count(mid):
    start = spot[0]
    cnt = 1 # 최소 첫번째 지점에 말을 놓음
    
    for i range len(spot)-1:
        if (spot[i]-start)>mid:
            cnt+=1
            start=spot[i]
            
    return cnt

N, C = 5, 3

spot = [1,2,8,4,9]
spot = sorted(spot, reverse=False)

lt = spot[0]
rt = spot[-1]
res = 0

while lt<=rt:

    mid = (lt+rt)//2
    
    if C<=Count(mid):
        lt = mid+1
        res = mid
    else:
        rt = mid-1
    

print(res)

 

 

거의 비슷했다! 두 번째 값부터 비교하는 게 조금 더(?) 효율이 좋긴 하겠군