[Python] 11973번 Angry Cows (Silver)

 

https://www.acmicpc.net/problem/11973

 

11973번: Angry Cows (Silver)

---

 

22/11/05

 

 

전형적인 이분 탐색 문제로, 외국어 문제여서 문제를 해석하는 것이 어려운 문제이다.

---

 

문제 접근 방식:

 

 

먼저 외국어 문제이기에 문제 요약을 하자면 다음과 같다.

건초더미가 놓여있는 위치 $x_1, x_2, ..., x_n$이 주어져 있다. 우리는 건초더미를 모두 없애고 싶다.
x라는 위치에 소를 폭발시킨다고 하면, $[x-R, x+R]$ 구간의 건초더미가 모두 사라짐. 이때, $R$은 폭발 반경임.
건초 더미 $N$개가 주어져 있고, 소의 마리 수 $K$마리가 주어질 때, 건초더미를 모두 없앨 수 있는 최소 폭발 반경 $R$을 구해라.

문제를 보고 먼저 든 생각은, "건초더미가 놓여있는 위치를 입력받으면, 이를 정렬해야겠다"였다.

 

 

그 이유는 예제에 있었다.

 

예제 입출력을 도식화시키면 다음과 같이 도식화시킬 수 있다.

건초더미의 위치와 폭발반경

따라서, 이를 직접 구현하려면 리스트를 정렬해야겠다고 생각했기 때문이다.

 

 

그림에서 보다시피, 우리는 소를 폭발시키는 위치 $x$가 어디 있는지는 잘 모르지만 $2R$만큼의 구간이 사라진다는 사실을 잘 알고 있다.

 

때문에, $R$을 최소화하기 위해서는 그림과 같이 처음 없어지는 건초 더미가 최대한 폭발 반경의 끝에 위치해있어야 한다.

 

이 그림에서는 1부터 11까지 전부 다 사라진다는 것을 알 수 있다.

 

이후, 18부터 건초 더미가 다시 있으므로, 18부터 시작해 $2R$, 즉, 10만큼 해당하는 구간이 전부 사라진다.

 

그래서 모든 건초 더미를 없앨 수 있다.

 

 

다른 예제라면, 이를 계속 반복하는 과정을 거칠 것이다.

 

이렇듯, 이 과정은 폭발 반경을 $R$이라고 가정했을 때 들판 위에 놓인 건초 더미를 없애는 한 번의 시뮬레이션 과정이다.

 

이 시뮬레이션 과정을 통해서 우리는 폭탄(소)이 얼마나 많이 필요할지 얻어낼 수 있다.

 

 

만약 소가 원래 주어진 소의 양보다 많이 쓰이게 끔 나온다면, 그것은 폭발 반경이 너무나도 작아서 건초 더미를 잘 없앨 수 없는 것이므로 폭발 반경을 늘려서 다시 시뮬레이션을 돌려야 된다.

 

만약 소가 원래 주어진 소의 양보다 작게 쓰인다면, 그것은 폭발 반경이 너무나도 커서 건초 더미를 한 방에 없앤 것이므로, 우리는 폭발 반경의 최솟값을 없애는 것이 목적이기 때문에 폭발 반경을 줄여서 다시 시뮬레이션을 돌려야 한다.

 

만약 소가 원래 주어진 소의 양과 같게 쓰인다면, 그것은 적절하게 소가 쓰인 것인데, 우리는 그중에서도 가장 작은 폭발 반경을 탐색하고 싶기 때문에 폭발 반경을 줄여서 다시 시뮬레이션해야 한다.

 

 

근데, 이렇게 일일이 폭발 반경을 1씩 늘리고 줄여가며 탐색하면, 건초 더미가 놓인 위치의 최댓값이 10억까지이기 때문에, 최악의 경우 폭발 반경을 5억으로 해야 할 수도 있다.

 

다시 말해, $O(n)$의 시간 복잡도를 가지고 최솟값을 찾아내려는 과정을 진행하려고 한다면 시간 초과가 날 수 있다는 것이다.

 

 

때문에, 나는 이를 이분 탐색으로 구현하면 좋을 것 같다고 생각했다.

 

위의 조건을 그대로 가지고 와서, 이 한 번의 시뮬레이션을 통해 얻어낸 소의 양을 통해 기존의 범위보다 더 큰 범위에서 탐색할지, 작은 범위에서 탐색할지를 판단하였다.

 

건초 더미 리스트는 최대 크기가 5만이고, 한 번의 시뮬레이션은 $O(n)$의 시간이 걸린다.

 

그리고 이분 탐색은 $O(log n)$의 시간 복잡도를 가지는데, 최악의 경우 폭발 반경이 5억이 될 수도 있으므로, 기껏 해봤자 29번 반복한다.

 

따라서 최악의 경우, 5만*29번을 반복하여 연산하기 때문에 충분히 통과할 것이라고 추측할 수 있다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 11973번 Angry Cows (Silver)
# 이분 탐색, 정렬
'''
문제 요약:
건초더미가 놓여있는 위치 x1, x2, ..., xn이 주어져 있다.
우리는 건초더미를 모두 없애고 싶다.
x라는 위치에 소를 폭발 시킨다고 하면, [x-R, x+R]구간의 건초더미가 모두 사라짐.
이때, R은 폭발 반경임.
건초 더미 N개가 주어져 있고, 소의 마리 수 K마리가 주어질 때,
건초더미를 모두 없앨 수 있는 최소 폭발 반경 R을 구해라.

접근 방법:
먼저 건초더미가 놓여있는 위치를 정렬함.
x가 어디 해당하는지는 모르지만, 우리는 2R에 해당하는 구간의 건초더미가 사라짐을
알 수 있음.
때문에, 제일 작은 위치에 있는 건초더미를 없앤다면,
제일 작은 위치 + 2R까지 건초더미가 다 사라짐.
이후 아직 안없어진 건초 더미 중 제일 작은 위치에 있는 건초더미 없앰.
그 위치 + 2R까지의 건초더미 없앰. ...
계속 반복한다.

건초더미의 위치가 10억까지 이므로, 10억을 일일히 브루트 포스로 돌리긴 힘들다.
따라서 이분탐색으로 찾아보자.
'''
import sys
input = sys.stdin.readline

N, K = map(int, input().rstrip().split())  # 건초 더미의 개수와 소의 마리 수
hale = sorted(int(input()) for _ in range(N))

def binary_search(low, high):
    mid = (low+high)//2
    if low >= high:
        return mid
    else:
        exploded_cow = 0  # 소가 몇 마리 쓰이는가?
        hale_index = 0  # hale의 인덱스
        while True:
            hale_pos = hale[hale_index]
            for i in range(hale_index, N):
                if hale[i] > hale_pos + 2*mid:
                    exploded_cow += 1
                    hale_index = i
                    break
            else:
                exploded_cow += 1
                break
        if exploded_cow <= K:
            return binary_search(low, mid)
        else:
            return binary_search(mid+1, high)

R = binary_search(hale[0], hale[-1])
print(R)