<백준 2110번-python> 공유기 설치

풀이 시간 : 50분

시간 제한 : 2초

메모리 제한 : 128 MB

출처 : 백준-2110번 https://www.acmicpc.net/problem/2110

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

내가 적어본 문제 풀이

처음에 접근했던 방법은 집을 기준으로 와이파이를 설치할 최적의 자리를 찾는 방식이었다.

예를 들어, 집의 좌표들을 정렬하면 항상 2개의 와이파이는 처음 집과 끝 집에 설치하는 것이 가장 최대 거리가 되므로 C=2면 양 끝에 설치하는 것이 기본 전제다.

그 다음 와이파이들은 양 끝에서 동일한 거리가 떨어진 위치에 설치하는 것이 최선인데, 이는 수직선 상의 양 끝을 기준으로 일정한 등분을 나눈 꼭지점들이 된다.

따라서 집의 양 끝 거리에서 C-1만큼을 등분한 뒤, 그 꼭지점들이 최선의 와이파이 설치 장소라고 생각하고 그 장소들과 가장 가까운 집들을 하나 씩 찾아가는 방법이다.

그런데 이 방법을 사용하면 가장 가까운 집들을 찾는 과정에서 오버헤드가 상당히 발생하고, 중복 제거도 까다롭다.

결론적으로 가장 효울적이고 올바른 접근 방법은 집이 아니라 거리에 기준을 두는 것이다. 설치해야 할 와이파이들을 최소한 d만큼 떨어뜨려 설치한다고 하자. 그리고 집들의 좌표를 정렬한 리스트는 house다.

그럼 가장 먼저 와이파이를 설치할 집은 항상 house[0]이 된다.

그 다음 설치할 집을 찾아야 하는데, 그 집은 최소한 d만큼 떨어져 있어야 하므로 house[i] - house[0] >= d이면 설치한다.

이때 와이파이의 개수를 세어 C 이상이면 조건보다 와이파이를 많이 설치한 것으로 더 넓게 설치해볼 수 있으므로 d를 늘려보고, C 이하면 좀 더 촘촘히 설치해야 하므로 d를 줄여나간다.

그럼 초기 d값을 어디로 시작해서 찾아갈 지가 고민인데, 위에서도 말했듯이 와이파이를 설치할 수 있는 가장 최대 거리는 양 끝집에 설치하는 것이고, 반대로 최소 거리는 조건에 나와있는 한 칸이다.

따라서 양 끝의 기준이 있으므로 이진 탐색을 이용해 d를 설정하는 것이 가장 효율적이다.

min_d = 1
max_d = house[-1] - house[0]
finded_min_d = 0
while min_d <= max_d:
    d = (min_d + max_d) // 2
    now_house = house[0]
    wifi_cnt = 1
    for next_house in house[1:]:
        wifi_d = next_house - now_house
        if wifi_d >= mid_d:
            wifi_cnt += 1
            now_house = next_house
    if wifi_cnt >= C:
        finded_min_d = d
        min_d = d + 1
    else:
        max_d = d - 1

결국 위 while문을 다 돌면 이진 탐색이 완료되고, 최종적으로 finded_min_d에 가장 인접한 와이파이 사이의 최대 거리가 저장된다.

이 문제는 어떤 변수나 조건을 기준으로 풀어나갈 지 고민하는 것이 얼마나 중요한 지 알려줬다.

전체 소스코드 - https://github.com/on1ystar/algorithm-problem-solving-codes/blob/master/binary-search/공유기 설치.py