[이진탐색] 공유기 설치

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 50분 + a

1. 문제 설명

- 공유기를 설치해야 하는데 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하는 문제

2. 접근 방식

- 초기에는 공유기를 끝과 끝에 배치하고, 이진탐색을 하면서 남은 공유기를 배치하려고 했다.

- 그리고 공유기를 배치한 것들의 차를 구해서 가장 최대인 거리를 구하려고 했으나...답이 아니었다.

---

- '가장 인접한 두 공유기 사이의 거리'의 최댓값을 탐색해야 하는 문제로 이해해야 한다'고 하는데 사실 아직까지도 이해가 잘 안되긴 한다...

- 아무튼 '가장 인접한 두 공유기 사이의 거리'를 조절해가며 매 순간 실제로 공유기를 설치해 C보다 많은 개수로 공유기를 설치할 수 있는지 체크해 문제를 해결할 수 있다.

- C보다 많은 공유기를 설치할 수 있다면 '공유기 사이의 거리의 값'을 증가시켜서 더 큰값에 대해서도 성립하는지 체크하기 위해 다시 탐색을 수행한다. 

3. 코드

- 초기 내 코드_ Fail

# import sys
# # 짝수, 홀수 나눠서 와이파이 삽입
# input = sys.stdin.readline
import heapq

n, m = map(int, input().split())
ls = []
for _ in range(n):
    ls.append(int(input()))
ls.sort()

wifi = []
heapq.heappush(wifi, ls[0])
heapq.heappush(wifi, ls[-1])
remain = m - 2

start, end = 0, (n-1)

def binary(start, end, remain):
    if start > end or remain == 0:
        return None
    mid = (start+end) // 2
    if remain % 2 == 0: #W 짝수일 때
        binary(start, mid, remain//2)
        binary(mid+1, end, remain//2)
    elif remain % 2 == 1: #홀수일 때
        heapq.heappush(wifi, ls[mid])
        remain -= 1
        binary(start, mid-1, remain//2)
        binary(mid+1, end, remain//2)
        
binary(0, n-1, remain)
answer = 1e9
a= heapq.heappop(wifi)
while len(wifi) > 0:
    b= heapq.heappop(wifi)
    answer = min(b-a, answer)
    a = b
print(answer)

- 해답 코드

n, c = map(int, input().split())
array = []
for _ in range(n):
    array.append(int(input()))
array.sort()

start = array[1]-array[0]
end = array[-1]-array[0]
result = 0
while(start <= end):
    mid = (start+end) //2
    value = array[0]
    count = 1
    for i in range(1, n):
        if array[i] >= value+mid:
            value = array[i]
            count+=1
    if count >= c: # C개 이상의 공유기를 설치할 수 있는 경우, 거리를 증가
        start = mid+1
        result = mid
    else:
        end = mid-1
print(result)

 

4. 코멘트

- 사실 해당 문제의 경우 아직까지도 세부적으로 이해가 좀 부족한 것 같다. 조금 더 이해가 필요해 보인다.

- 내 코드 사실...만족했는데 또 해답코드 보니까 아닌건 아니더라...솔직히 이진탐색 너무 만만하게 봤다...