boj.kr/2110 공유기 설치 (gold4) 파이썬 풀이

1. 집 좌표 리스트를 정렬한다.

2. 집들에 대한 최소거리(1), 최대거리(첫번째 집에서 마지막집까지 거리) 를 구한다.

3. 최소 거리가 최대거리보다 작거나 같으면 아래 4-7을 반복한다.

4. 최소 거리와 최대 거리의 중간값을 계산하고 첫번째 집에 공유기를 설치한다.

5. 집 좌표 목록을 순회하면서 현재 공유기 설치한 집 + 중간값 이상의 좌표에 있으면 공유기를 설치하고 카운트를 1 증감한다.

6. 공유기 개수 이상으로 설치되었으면 거리를 넓힌다. (최소거리 = 중간값+1) result에 중간값를 저장한다.

7. 공유기 개수보다 적게 설치되었으면 거리를 좁힌다. (최대거리 = 중간값-1)

8. result를 출력한다.

 

N, C = map(int, input().split())
homes = [int(input()) for _ in range(N)]
homes = sorted(homes)

lo = 1
hi = homes[-1] - homes[0]
result = 0

while lo <= hi:
    mid = (lo + hi) // 2
    cur = homes[0]
    cnt = 1
    for i in range(1, len(homes)):
        if homes[i] >= cur + mid:
            cur = homes[i]
            cnt += 1
    if cnt >= C:
        lo = mid +1
        result = mid
    else:
        hi = mid -1

print(result)

 

참고출처

"[python] 백준 2110 - 공유기 설치", hyojeong94.tistory.com, 2022년 2월 21일 수정, 2023년 5월 23일 접속,

https://hyojeong94.tistory.com/151.