Python - [백준]2110-공유기 설치

출처

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

문제

공유기를 c개 놓을때, 가장 멀리 배치할 수 있는 거리를 출력하는 문제이다.

접근방법

처음에는 이분탐색을 왜 쓰지? 하다가 배열의 인덱스 번호로 접근하여 이분탐색을 진행하려고 하다 실패하였다. 그렇게 접근하다보니 이분탐색이 더 이유가 없다는걸 발견하고 생각하던 중 생각이 났다.
배열의 인덱스랑 집 거리가 아니라, 임의의 거리를 두고 모든 집에 배치를 했을때, 그 배치 거리를 정해서 이분탐색으로 하면 바로 풀리겠다는 생각이 들었다. 결국 배치 거리를 구하는게 핵심이기 때문이다.

풀이

우선 배열을 받은 뒤 정렬하고, start를 최소 거리인 1로 두고 end는 첫번째 집과 마지막 집의 거리차이로 하였다.
그 중간값을 mid로 하여, mid보다 거리가 가까운 집은 설치하지 않고 먼 집만 설치하였을때 몇 개를 설치 할 수 있는지를 구하여 만약 설치를 다 못했다면 mid 위로는 볼 필요가 없으니 end를 mid - 1로 두고, 설치를 진행했는데 목표치 보다 많다면 start를 mid + 1 로 두고 이분탐색을 진행하였다.

요약하자면,

1. 배열 받은 뒤 정렬
2. start, end를 1과 가장 먼 거리인 arr[-1] - arr[0]으로 설정
3. for문으로 앞집부터 공유기를 설치
4. 설치한 공유기의 수가 목표치 보다 작다면 end는 mid - 1,
   크다면 start를 mid + 1 로 설정하여 탐색을 계속 진행

예제를 보면, 3개를 설치해야하고 최대로 먼 집의 거리는 8이다.
1과 8의 중앙값인 4를 두고 (바로 전에 설치했던 집의 좌표 + 현재 집의 좌표)가 현재의 거리의 최대값인 mid보다 크다면 -> 설치, 작다면 설치하지 않고 넘어간다.
첫번째에서는 4로는 두개밖에 설치 할 수없으니 end를 3으로 설정하고 다시 탐색을 진행하는 식이다.

코드

import sys
input = sys.stdin.readline

n, c = map(int, input().split())
arr = [int(input()) for i in range(n)]
arr.sort()

start, end = 1, arr[-1] - arr[0]
answer = 0
if c == 2:
    print(arr[-1] - arr[0])
else:
    while start <= end:
        mid = (start + end) // 2
        cnt = 1
        last_wifi = arr[0]
        for i in arr:
            if i - last_wifi >= mid:
                cnt += 1
                last_wifi = i
        if cnt >= c:
            answer = mid
            start = mid + 1
        else:
            end = mid - 1
    print(answer)