[BOJ/이분탐색] 2110 공유기 설치

문제링크

https://www.acmicpc.net/problem/2110

2110번: 공유기 설치

---

import sys

# 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램

house,wifi = map(int,sys.stdin.readline().split())

houses = []
for _ in range(house):
    houses.append(int(sys.stdin.readline()))


start = 1
houses = sorted(houses)
end = houses[-1] - houses[0] 
answer = 0
# 각 원소의 차?
# 제일 작은값부터 n개만큼 찾을건데 mid만큼 차이나는 값이 n개만큼 존재해야해
# 그니까 1시작해서 mid가 5니까 다음은 6이상이고 그럼 8이 선택되지
# 근데 그 다음값도 8+5 = 13이니 13이상인 값이 존재해야하는데 없어
# 2부터 시작해도 같은느낌
# 만약에 mid 값이 있다면 answer 업데이트하고 start = mid+1 없으면 end = mid -1



while start<= end:

    mid = (start+end)//2

    res = []
    res.append(houses[0])

    for house in houses:
       
       if house - res[-1] >= mid:
          res.append(house)


    if len(res) >= wifi:
        answer = mid
        start = mid+1

    else:
       end = mid-1

print(answer)

풀이

1. 이번에도 이분탐색을 풀어보았는데 위의 문제를 처음보았을땐 조합으로 모든 경우의수를 구하고 차이값들 중 최소를 구하는 법으로 생각했다. 이는, 원소개수가 최대 20만개라 조합을 사용하면 시간초과가 난다. 이럴 경우, 이분탐색을 생각해보자. 추가로 원소의 값이 말도안되게 10억 나온다면 더더욱 이분탐색이라 생각해보자

 

2. 이분탐색의 경우 풀이 유형은 거의 비슷하다 최소, 최대 찾고 while start<=end 구문 넣고 조건 확인한 다음 만족하면 start = mid + 1, 만족하지않으면 end = mid - 1 이런식

 

3. 위의 문제에서는 mid값만큼 차이가 나는 원소가 공유기 갯수만큼 존재하는지를 조건으로 설정했다. 이때, 첫 시작을 houses[0]으로 안하고 0이나 1로 해버려서 자꾸 틀렸었다. 추가로 answer을 갱신할때 어차피 탐색하면서 해당 값이 최댓값이기 때문에 max를 안넣고 바로 answer=mid로 가능했다.