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

[문제]

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

---

[풀이]

def Count(len): # 말이 들어있는 마구간 갯수
    cnt = 1 # 말 한 마리 배치
    ep = horses[0]  # 첫번째 마구간에 말 배치

    for i in range(1, n):
        if horses[i]-ep >= len: # 마지막에 배치한 지점과 현재 배치하려고 하는 지점의 거리 len 보다 크면
            cnt += 1    # 해당 위치에 말 배치 가능
            ep = horses[i]  # 마지막 말의 배치 지점을 바꿔줌
    return cnt  # 배치한 말의 마리 수를 리턴

n, c = map(int, input().split())

horses = []
res = 0
largest = 0

for _ in range(n):
    tmp = int(input())
    horses.append(tmp)

horses.sort()
lt = 1  # 두 말 사이의 거리가 가장 가까운 건 1
rt = horses[n-1]

while lt<=rt:
    mid = (lt+rt)//2

    if Count(mid) >= c:     # mid: 가장 가까운 말들의 거리
        res = mid
        lt = mid + 1    # 가장 인접한 두 마리 말의 최대 거리이므로, 답이라면 그것보다 더 짧은 거리는 당연히 답이 가능하니 더 큰 거리를 찾아줘야함
    else:   # 답이 되지 않는다면, 가장 인접한 두 마리 말의 거리가 너무 긴 것이므로 원하는 c마리의 말을 배치하지 못함
        rt = mid - 1    # 거리를 줄여줘야 하므로 더 긴 쪽은 답이 되지 않음

print(res)

---

[내용]

- Count 함수 구현이 이해되지 않아서 아예 접근 조차 하지 못했다..

  = Count 함수는 말이 들어있는 마구간의 갯수를 리턴함. => Count 함수의 리턴값이 c보다 크거나 같다면 해당 거리가 가능하다는 뜻

- 무엇을 변수로 두어야 할 지에 대한 판단이 미흡했다. => 거리를 변수로!

   = 가장 가까운 두 말의 최대 거리를 알아야 하므로 거리에 대해 범위를 정하면서 결과값을 알아야 함

   = mid 값은 가장 가까운 말들의 거리를 의미함

 

<알고리즘 설명>

1, 2, 4, 8, 9 

1) lt =1, rt=9 이고 1번말이 1 위치에 있을 때

- mid(가장 가까운 말들의 거리) = 5: 가장 가까운 두 말의 최대 거리. = 모든 말들의 거리는 5보다 크거나 같아야 한다!

- 2번말은 2에 있을 수 없음: 두 말의 거리가 2-1 > 5 이므로 2번말은 8의 위치에 있어야 함 

- 3번말을 놓을수가 없음

2) 1)이 성립하지 않으므로 mid(가장 가까운 말들의 거리)를 줄여야 함. -> rt=4로 수정