나의 풀이
N, C = map(int, input().split())
homes = []
for i in range(N):
homes.append(int(input()))
homes.sort()
start = 1 # 최소 거리
end = homes[-1] - homes[0] # 최대 거리
def binary_search(arr, start, end):
while start <= end:
count = 1 # 첫 번째 집은 이미 설치되어있다고 가정
last_locate = homes[0]
mid = (start + end) // 2
for x in arr:
if last_locate + mid <= x:
last_locate = x
count += 1
if count >= C:
start = mid + 1
else:
end = mid - 1
return end
print(binary_search(homes, start, end))- N, C 그리고 집의 좌표들을 입력받고 homes 리스트에 넣어준다.
- 이분 탐색을 하기 위해서는 오름차순 정렬은 필수이기 때문에 정렬을 해준다.
- 공유기를 설치할 수 있는 집들간의 간격을 구할 것이다. 그렇기 때문에 start 는 최소 간격인 1, end 는 가장 큰 집의 좌표와 가장 작은 집의 좌표를 뺀 값을 담아준다.
- start 가 end 보다 커질 때까지 반복한다.
- 우선 첫 번째 집의 좌표에 공유기를 설치해두고, 이 집을 기준으로 중간 간격을 더했을 때 이 둘의 합보다 크다면 공유기를 설치할 수 있는 집이된다.
- 때문에 우선 첫 번째 집의 좌표에는 공유기가 설치되어 있기 때문에 count 를 1로 두고, last_locate(공유기가 설치된 마지막 집의 좌표) 를 homes[0] 으로 둔다.
- 이제 homes 배열을 돌면서 last_locate + mid 보다 크거나 같다면 count += 1을 해주고, last_locate 를 해당 집의 좌표로 바꿔준다.
- 만약 count 가 C 보다 크거나 같다면, 이는 간격을 넓혀야 한다는 의미이므로 start = mid + 1을 해준다.
- 아니라면 간격을 좁혀야 하기 때문에 end = mid - 1 을해준다.
- 반복문이 종료되면 최대값이 되는 end 를 리턴해준다.
느낀점
처음에 문제를 읽었을때 이해가 되지 않아서 한참을 해보다 검색을 해보았다. 코드를 보니 그동안 풀었던 이분 탐색의 구조에서 크게 벗어나지 않는 문제였다.
