[백준] 2110 : 공유기 설치 python

 

이분탐색 문제들은 어떤 값을 이분탐색할 것인지 결정하는 게 가장 어려운 것 같다...

 

이 문제는 공유기 사이의 거리값으로 이분탐색을 해서 풀어야 하는 문제였다.

 

# 집의 개수와 공유기의 개수를 입력받음
n,c= map(int,input().split())
# 집의 좌표들을 입력받고 정렬한 리스트 house를 생성
house = sorted([int(input()) for _ in range(n)])

# 공유기 사이의 거리값들을 이분탐색 하는 것이기 때문에
# 최소거리인 1과 최대거리인 house[-1]-house[0]을 start와 end로 지정함
start,end = 1, house[-1]-house[0]

# 인접한 공유기의 거리의 최대값을 저장할 변수
answer = 0

# 이분탐색이 가능할 동안 반복함
while start<=end:
	# 중간값
    mid = (start+end)//2
    # 0번째집에 공유기를 설치하고 시작함
    current = house[0]
    cnt = 1

	# 1~n-1번째까지
    for i in range(1,n):
    	# 현 위치와 다음 집까지의 거리가 mid 이상이라면
        if house[i]-current>=mid:
        	# 공유기를 설치하고
            cnt +=1
            # 현 위치를 갱신함
            current = house[i]
            
   	# 일단 공유기 설치를 끝냈는데, 설치한 개수>=주어진 공유기 개수라면
    # 간격을 더 넓혀야 한다는 뜻임
    # answer(=인접한 공유기의 최대값)보다 새로운 거리가 더 크다면
    # answer를 갱신하고
    # start를 mid+1로 변경해 다시 이분탐색을 함
    if cnt>=c:
        if answer<mid:
            answer = mid
        start = mid+1
    
    # cnt<c는 공유기를 더 설치해야 한다는 뜻이므로 탐색할 간격을 좁혀야 함
    else:
        end = mid-1

print(answer)

 

 

11/07에 다시 풀어봤음.

n,c=map(int,input().split())

data = sorted([int(input()) for _ in range(n)])

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

while start<=end:
    mid = (start+end)//2
    current = data[0]
    cnt = 1
    
    for i in range(1,n):
        if data[i]-current>=mid:
            cnt +=1
            current = data[i]
    if cnt>=c:
        result = mid
        start = mid+1
    else:
        end = mid-1
print(result)