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

(문제) 마구간(결정알고리즘)

---

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)가 한 줄에 하나씩 주어집니다.

출력설명

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

테스트케이스

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

---

해결방법

문제가 이해되지 않을 수 있으니 마구간을 기준으로 시각화 해보자!

우리는 마구간이 테스트케이스 처럼 있다고 가정을 하자

위의 그림처럼 나타낼 수 있다.

구하려고 하는 것은 말 끼리 가장 멀리 떨어져 있는 구간에서 가장 가까운 마구간의 거리가 최대!

정답에서 알고 싶어하는 것은 위의 그림처럼 의미하는 것이다.

이것을 구하기 위해서 이분탐색을 사용할 것이다!

일단 이분탐색을 하기 전에 어떤 식으로 접근해야하는지 생각을 하자.

이분 탐색을 이용하기 전, 문제 해결에 이해하기 더하기 위해 순회를 이용하여 문제를 풀도록 가정 해보자!

순회의 시작은 마구간의 가장 작은 위치 부터 가장 큰 위치까지를 범위를 잡을 것이다.

그러고 1부터 순회하여 모든 말이 마구간과 마구간 사이의 길이가 1 이상이면 들어간다고 생각하면 된다.

처음 마구간에는 무조건 말이 들어갈 수 있으므로 일단 말을 처음 마구간에 넣는다.

그러면 시작이 마구간 1이므로 다음 마구간과 거리를 뺀다.

다음 마구간은 2이므로 2 - 1을 하여 1이라는 것을 알 수가 있다.

이 의미는 말이 다음 마구간2에 들어갈 수 있는 의미이므로 말을 하나 추가한다.

또 그 다음 마구간을 확인 한다. 마구간4에 들어갈 수 있는지 전의 마구간2와 비교한다.

4 - 2 = 2 이므로 마구간 사이의 길이 1이상이므로 말이 들어갈 수 있다.

이렇게 모든 말을 넣었으면 마구간과 마구간 사이의 길이가 1을 사용할 수 있음을 확인했다.

이런 식으로 1부터 순회해 9까지 확인을 하는데, 순회하는 도중 만약에 말이 전부들어 갈 수 없다면 순회를 끝내고 구한 마구간과 마구간 사이의 길이 중에서 가장 큰 것이 정답이다!

안되는 경우는 경우를 한번 살펴보자.

만약 마구간과 마구간 사이의 길이가 5 이상이면 말이 들어간다고 가정을 하자.

처음 마구간에는 무조건 말이 들어가므로 마구간1 부터 시작을 한다.

다음 마구간과 마구간1 거리를 비교한다. 마구간2 - 마구간1 = 1

길이가 1 밖에 안되므로 5 이상이 만족하지 않아서 마구간2는 무시한다.

그 다음 마구간4를 비교한다. 4 - 1 = 3, 이 또한 5 이상을 만족하지 않아 마구간4를 무시한다.

마구간8 - 마구간1 = 7 이 마구간에는 말이 들어갈 수 있다 5 이상을 만족하므로, 말을 집어 넣는다.

그 다음 마구간9 와 마구간8을 비교했는데, 거리가 1이 나왔다. 이러면 말이 들어갈 수가 없다.

지금 들어가야하는 말이 총 3 마리 인데, 2마리 밖에 들어가지 않았다… 이런 경우가 가장 먼저 생기는 순간 끝을 내는 것이다.

이렇게 들어갈 수 있는 것 중에서 가장 큰 수를 이용하면 되는 것이다.

하지만!!!

순회 탐색을 통해서 찾으면 값이 엄청 많을 경우 시간이 너무 오래 걸린다.

그래서 이분 탐색을 이용해서 찾는다.
(이분 탐색은 그림을 따로 넣지 않겠다)

이분 탐색을 이용해서 찾는 방법을 이제 설명해 볼 것이다.

말이 들어갈 수 있는 마구간과 마구간의 거리 중 LT를 가장 작은 거리로 잡고, RT를 가장 큰 거리의 경우를 잡는다.

이제 이분 탐색의 매력적인 MID를 (LT + RT) // 2 를 통해서 중앙을 구한다.

LT 가 1이고, RT 가 9라고 가정을 하자, 그러면 MID 는 5가 된다.

5를 이용하여 말을 배치하면, 말은 총 2마리 밖에 들어갈 수 없다.

이것을 알았으므로 말이 더 많이 들어가야하니 마구간과 마구간의 거리를 조금 줄여준다.

그러면 RT를 MID - 1로 설정하면 된다.

다시 반복하여 1 ~ 4 그 사이 2를 구하게 된다.

2는 말이 총 3마리 전부 들어갈 수 있다! 그렇기 때문에 2라는 거리를 저장해 놓는다.

더 큰 거리가 존재할 수 있으므로 저장하는 것이다.

이제 더 큰 거리를 찾아보기 위해서 LT를 MID + 1로 변경시킨다.

2 ~ 4 그 사이는 3이 된다.

3 또한 3마리 전부 들어갈 수 있다. 기존에 저장 되어있던 거리 즉 2가 3보다 작으면 3을 저장한다.

이렇게 반복하다가 LT 가 RT 보다 커지거나, RT 가 LT 보다 작아지는 경우가 생길 것이다.

이때 반복을 끝낸 후, 저장 했던 거리를 출력하면 그 것이 정답이 된다!

---

코드

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

arr = [int(input()) for i in range(n)]

# 마구간 정렬
arr.sort()

# 말 간격 가정하기
# 최소 간격으로 들어갈 수 있는 경우
LT = arr[0]
# 최대 간격으로 들어갈 수 있는 경우
RT = arr[-1]

# 말을 수직선 상으로 가정
# 무조건 첫 말은 처음에 들어갈 수 있다.
# 최대 거리 저장
res = 0

while LT <= RT:
    # 첫말로 시작
    b_horse = arr[0]
    horse = m - 1
    MID = (LT + RT) // 2
    s = 1
    # 말이 존재하고 마굿간 개수 까지만
    while horse and s < n:
        if arr[s] - b_horse >= MID:
            # 후에 있는 것을 비교하기 위해서 저장
            b_horse = arr[s]
            # 말 추가
            horse = horse - 1
        s = s + 1
    
    # 말이 남아 있으면 MID가 너무 큰것이니 줄여야 한다
    if horse:
        RT = MID - 1
        continue
    else:
        LT = MID + 1

    if res < MID:
        res = MID

print(res)