📚 2110 - 공유기 설치

공유기 설치

이해

이분탐색 문제이다.
다만, 문제 이해하는데 시간이 많이 걸린 것 같다.
공유기 설치 길이를 움직이며(이분 탐색을 한다.) 적절한 집에 설치가 가능한지 살펴보는 문제이다!

(1) 첫 집을 start, 첫 집과 끝 집 거리를 end로 둔다.
(2) 첫 집과 끝 집 이분 탐색을 진행한다. (설치 길이를 이분 탐색 기준으로 한다.)
(3) 매번 첫 집부터 탐색을 하며 공유기 개수를 둘 수 있는지 확인한다. 설치 길이를 더해서 그 다음 거리에 집이 있는지 확인하는 형식이다. for문
(4-1) 만약, 거리에 해당되는 공유기의 개수가 시작전 원하는 공유기의 개수보다 많거나 같다면 시작지점에 += 1을 한다.
(4-2) 아니라면, 공유기 개수가 더 필요하므로 end에 mid - 1을 한다. (설치 길이를 줄여야한다. (start + end) // 2가 mid 값이 되므로 )

소스

import sys

INF = 1e9

read = sys.stdin.readline

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

arr = []
answer = 0

for _ in range(n):
    arr.append(int(read()))

arr.sort()

start, end = 1, arr[-1] - arr[0]

while start <= end:
    mid = (start + end) // 2

    count = 1
    cur_house = arr[0]  # 시작점
    for i in range(1, n):
        if cur_house + mid <= arr[i]:
            count += 1
            cur_house = arr[i]

    if count >= c:
        answer = mid
        start = mid + 1
    else:
        end = mid - 1

print(answer)

채점 결과

똑같은 코드를 두 번 돌렸을 때 하나는 192ms, 하나는 216ms가 되었다. (채점 데이터가 랜덤인 것 같다.)

참고 : https://claude-u.tistory.com/448