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

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

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

출력

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

 

 

필요한 도구

 

 

1. 이분 탐색 알고리즘 - 좌, 우측 탐색 : 찾는 값이 없을 경우 가장 근접한 방향의 값을 출력하거나, 값이 여러 개일 경우에 가장 좌, 우측의 값을 출력한다.

 

[Python] 백준 - 1654 랜선 자르기

- 이분탐색의 최대값(우측) 찾기 포스팅

 

문제해결방법

 

 

 

1. 이분 탐색에서 최댓값을 찾는 방법은 위 포스팅을 참조하자. 이분 탐색 알고리즘의 구조는 같고, 변동되는 mid값을 이용해 한 번 더 가공하여 주어진 target값과 비교하는 거다.

 

우측 탐색(최댓값)은 target값과 같다는 조건 하에 최댓값을 찾거나, 조건이 맞을 때 같은 원소가 많을 경우, 가장 우측(최댓값)을 가리키도록 한다. (정렬의 방법이 반대면 좌측 탐색과 같다.)

 

2. mid값을 가공하는 방법을 생각해보자. mid값은 l , r 의 변화에 따라 달라진다. 이를 변동하는 거리라고 놓고, 이 거리에 따라 주어진 공유기 갯수를 만족시키는지 확인하고, 그 범위 안에서 최댓값이 맞는지 확인하면 된다.

 

1) 첫번째집에서 mid값(거리)을 더하고, 설치한 거리가 짧으면 다음 집에는 설치를 해야한다. (cnt += 1) 기준을 설치한 다음 집으로 옮기고, 반복하면 공유기 설치 갯수가 나온다.

 

if cnt == target:
    l = mid+1
elif cnt > target:
    l = mid+1
else:
    r = mid-1

- 우측 탐색(최댓값) 확인하기 

 

2) cnt가 target과 같아도, 최댓값을 찾아야 하니, mid길이를 올려본다. ( l = mid + 1 )

 

a. 최댓값이 맞으면 r은 계속 줄어들다가,  l - 1 이 된다. 

b. 최댓값이 아니면 r이 줄어드는 과정에 l 의 변동 ( l = mid + 1 )이 생기고, 결국 a처럼 된다.

 

 

- 코드

import sys
from collections import deque
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

n, c = map(int, input().split())
city = sorted([int(input()) for _ in range(n)])

def binary_search(d, k):
    l, r = 0, d[-1]-d[0]
    while True:
        if l > r:
            return l - 1
        mid = (l+r)//2
        home = d[0]
        cnt = 1
        for i in range(1, n):
            if home+mid <= d[i]:
                cnt += 1
                home = d[i]
        if cnt == k:
            l = mid+1
        elif cnt > k:
            l = mid+1
        else:
            r = mid-1

print(binary_search(city, c))