baekjoon 2110: 공유기 설치

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

2110번: 공유기 설치

---

이진탐색문제

 

문제의 keyPoint는 st와 ed를 어떻게 두냐에 따른것 같다(정확힌 mid값이 정의하는 것이 무엇이냐에 따름)

 

내 코드의 경우.. mid값은 임의의 사이거리를 의미하고,

 

사이거리에 맞춰 cnt 갯수를 가지며, 문제에서 주어진 c와 cnt의 크기를 비교하여 mid값을 조정하면 된다

n,c = list(map(int,input().split()))
arr = []
for _ in range(n):
    arr.append(int(input()))
arr.sort()

st = 1
ed = arr[-1] - arr[0]
while st <= ed:
    # mid는 임의의 사이거리
    mid = (st + ed) //2
    cnt = 1
    router = arr[0]
    for i in range(1,n):
        #핵심
        if arr[i] - router >= mid:
            cnt+=1
            router = arr[i]
    if cnt >= c:
        st = mid +1
        l = mid
    else:
        ed = mid -1
print(l)