[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

5 3
1
2
8
4
9

예제 출력 1

3

힌트

공유기를 1, 4, 8 또는 1, 4, 9에 설치하면 가장 인접한 두 공유기 사이의 거리는 3이고, 이 거리보다 크게 공유기를 3개 설치할 수 없다.

 

소스코드

n, c = map(int, input().split())
li = []

for i in range(n):
    li.append(int(input()))
li.sort()	# 집의 위치를 오름차순 정렬

start, end = 1, li[-1] - li[0]	# start에 가능한 최소 길이, end에 가능한 최대 길이를 할당
while start <= end:	# 이분 탐색을 이용하여 공유기의 개수에 해당하는 거리의 최댓값을 구함
    cnt = 1	# 공유기의 개수를 세는 변수 선언
    mid = (start + end) // 2	# 거리를 나타내는 변수
    now = li[0]
    for i in range(1, n):
        if li[i] >= mid + now:	# 현재 공유기에서 거리만큼 더한 값보다 다음 공유기의 위치가 더 멀리 있을 경우, 새로운 공유기를 설치해야 함
            cnt += 1
            now = li[i]	# 새로운 공유기를 현재 위치로 할당함
    if cnt >= c:	# 공유기가 원하는 개수보다 많거나 같으면, 시작점을 mid + 1로 설정하여 더 긴 거리로 탐색함
        start = mid + 1
        result = mid	# 공유기 개수 c를 만족하는 경우 중 거리가 최대일 때를 구해야 하므로, 이 조건을 만족하는 값을 result에 저장
    else:	# 공유기가 원하는 개수보다 적으면, 끝점을 mid - 1로 설정하여 더 짧은 거리로 탐색함
        end = mid - 1

print(result)

1. 집의 위치를 입력받아서 오름차순으로 정렬합니다.

2. now에 맨 앞 집의 위치, start에 두 공유기 사이의 최소 거리, end에 최대 거리를 저장하고 두 공유기 사이의 거리를 찾기 위해 이진 탐색을 수행합니다.

    2-1. 맨 앞 집부터 공유기를 설치하고, 설치 가능한 공유기의 개수를 구합니다.

    2-2. 설치 가능한 공유기 개수 > c 이면, 두 공유기 사이의 거리를 더 길게 해주기 위해 start = mid + 1로 설정합니다.

    2-3. 설치 가능한 공유기 개수 < c 이면, 두 공유기 사이의 거리를 더 짧게 해주기 위해 end = mid - 1로 설정합니다.

    2-4. 설치 가능한 거리의 최댓값을 구해야 하므로,

        2-4-1. 2-2의 경우에 등호를 붙여주고 (설치 가능한 공유기 개수 >= c)

        2-4-2. 현재 두 공유기 사이의 거리인 mid를 result에 저장합니다.

3. result를 출력합니다.

 

 

출처 : https://hongcoding.tistory.com/3