[이코테/이진탐색/백준] 공유기 설치(정답,풀이)

문제 

2110번: 공유기 설치

 

정답

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

start = 1
end = array[-1] - array[0]
result = 0

while start <= end:
    mid = (start+end)//2
    value = array[0] # 첫 집에 공유기를 설치
    count=1 # 공유기 설치 개수
 
    for i in range(n):
        if array[i] >= value + mid :# 공유기를 설치할 수 있는 집이면 설치
            value = array[i] # 다음 공유기 설치를 위해 이전에 공유기를 설치한 집의 인덱스를 value에 저장
            count +=1 
    # 공유기 설치가 끝난 후 다음집으로 어디를 탐색할건지 지정
    if count >= c: # c개보다 많이 설치했다면 덜 설치해도 되는 것 = 거리를 더 늘일 수 있는 것 = 높은 쪽 탐색
        start = mid + 1
        result = mid # 일단 설치가 되는거니까 결과값에 저장. 설치를 반복해보며 최적의 해로 갱신될 것임
    else: # c개 미만으로 설치해서 더 설치해야하는 것 = 거리를 더 좁힐 수 있다는 것 = 낮은 쪽 탐색
        end = mid-1

print(result)

 

풀이

# 이진 탐색으로 무엇을 찾을건지를 생각하하는게 중요! 
# 처음엔 c만큼 설치해야 하는 집을 이진탐색으로 구해야하나 싶어서 삽질을 오래했는데
# 알고보니 만들 수 있는 거리를 찾아 구할 수 있는 문제였다.

# 일단, 주어진 공유기 설치 개수는 생각하지 않고
# 집과 집 사이의 거리는 최소 1에서 최대 (n-1)만큼의 거리를 가질 수 있다.
# (모든 집에 공유기를 설치했을 때 각 집 간의 거리는 1)
# (맨 처음과 끝 집에 설치했을 때 끝집-첫집 거리는 끝집번호 - 첫집번호 )

# 이제 반복문을 돌며 임의의 거리(x)를 정하고 x만큼의 거리마다 있는 집에 공유기를 설치해보는 것이다.
# 공유기 설치 작업이 끝났을 떄 설치된 공유기의 개수가 목표치 c보다 큰 지 작은 지에 따라 
# x보다 큰 쪽을 탐색해야 하는지, 작은 쪽을 탐색해야 하는지 알 수 있다. (이진탐색)

 

참고

이것이 취업을 위한 코딩테스트다(with. python)