공유기 - 이진 탐색 (파이썬)

사이트 링크 : https://www.acmicpc.net/problem/2110

 

문제는 아래와 같습니다.

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

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

출력

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

 

예제 케이스는 사이트에서 확인을 해보실수 있습니다

Input 
5 3
1
2
8
4
9

Output
3

 

이진탐색 문제 풀때 팁

• 답이 x 이상일수 있는가 ? 라는 질문에 대답을 할수가 있는지 
• 답이 x 이상이 아니다 -> x보다 작은 버위를 탐색
• 탑이 x 이상이다 -> 답이 x 보다 이상인 범위를 탐색

을 항상 머리속으로 생각하면서 문제를 풀어갈수 있어야 합니다. 

문제 해결 포인트 

• 가장 인접한 공유기 거리가 최대인것을 구하는 문제이므로
• 공유기가 n 개 이상 설치가 가능해야하고 
• n 개 가 설치가능한 거리중에서 이진 탐색으로 구하면 됩니다. 

정답코드 

n, c = map(int, input().split())
house = []
for _ in range(n):
    house.append(int(input()))
# 이진 탐색을 반드시 정렬이 되어 있는 상태에서 탐색 진행
house.sort()
# 정답의 최소는 1로 두기 (조건에 1이상이라 했으므로 거리는 1이상이여야 한다 )
start = 1
# 최대길의이 정답이 될수있는 값은 정렬된 첫번째 집의 좌표와 가장 끝의 좌표를 뺀 값의 거리이다 
end = house[-1] - house[0]
# 정답 
result = 0
while start <= end:
	# 이진 탑색 
    mid = (start+end) // 2
    # 첫번째 집에 설치했다고 가정
    value = house[0]
    # 설치된 횟수 
    count = 1
    for i in range(1, n):  # 순서대로 설치
        if house[i] >= value + mid:
            count += 1
            value = house[i]
    # 공유기 개수를 초과하였을때
    if c <= count:
        start = mid + 1
        result = mid  # 최적의 값을 저장
    else:
        end = mid - 1

print(result)

 

해당 코드를 실행해보면 아래와 같습니다. 

• start : 1, end : 8,mid : 4 => 1,8~에 설치 가능 
• start : 1, end : 3,mid : 2 => 1,4,8 에 설치 가능 
• start : 3, end : 3,mid : 3 => 1,4,8 에 설치 가능 

mid 값을 문제에서 탐색을 해야할 값으로 정해두고 이진 탐색을 하였습니다. 첫번째 집부터 순차적으로 설치한다는 가정하에 

 house 좌표가 마지막 공유기(value)가 설치된 좌표값에 mid 값을 더한 값이 보다 이상일때 설치를 하고 설치된 좌표를 value에 넣어 다음 좌표가 설치를 할수가 있는지 체크하는 식으로 진행하였습니다.