12015, 1300, 2110, 2805

2110. 공유기 설치

    X.sort()를 해준다
    임의의 거리를 두면서 공유기를 설치, 공유기의 총 개수(count)를 센다.
    count >= C --> 이때의 임의의 거리가 공유기 사이의 최대 거리가 된다

X.sort()
start = 1
end = X[-1] - X[0]
result = 0

while start <= end:
    mid = (start + end)//2 #공유기 사이의 거리

    count = 1 #설치한 개수
    ip = X[0]
    for i in range(1, N):
        if X[i] >= X[0]+mid:
            ip = X[i]
            count += 1

    if count >= C:
        start = mid+1
        result = mid
    else:
        end = mid-1


print(result)

---

1300. K번째 수

      N = 20, B[k] = 20 일때
      k값은 20보다 같거나 작은 원소들의 합
      
    행 1: 1*1 .... 1*20
      2: 2*1 .. 2*10
      3: 3*1 .. 3*6
      4: 4*1 .. 4*4
     	...
      9: 9*1 9*2
     10: 10*1 10*2
     11: 11*1
     	...
     18: 18*1 
     19: 19*1
     20: 20*1
     
     이때 B[k]//행 = 그 행에서 B[k]보다 같거나 작은 숫자의 개수(최대 N개)
	

start = 1
end = N*N
result = 0

while start <= end:
    preindex = 0

    mid = (start + end)//2 # 임의의 B[n]의 값

    for i in range(1, N+1):
        preindex += min(mid//i, N)

    if preindex >= k:  # k값이 작을때 = 임의의 B[n]이 B[k]보다 클때
        end = mid-1
        result = mid
    else:				# k값이 클때 = 임의의 B[n]이 B[k]보다 작을때
        start = mid+1

print(result)

---

12015. 가장 긴 증가하는 부분 수열2

	N번은 무조건 돌아야 함(하나씩 비교)
    
    1. list를 하나 만들어서 들어오는 값과 비교하여
    2. 가장 큰 값보다 크면 append,
    3. 작으면 list[i] < X <= list[i+1]위치 찾기 ==> 이분탐색
    4. list[i+1]위치에 값 삽입
    
    

---

2805. 나무 자르기

      나무의 수 = N, 나무의 길이 = M, 나무들 = trees
      
      M을 판별의 기준으로 한다
      start = 0
      end = sum(trees)
      mid = (start+end)//2 ==> 잘라야 하는 임의의 위치
      

result = 0
while start <= end:
    mid = (start + end) // 2
    s = 0

    for i in tree:
        if i > mid:
            s += i - mid

    if s >= M:
        start = mid + 1
        result = mid
    else:
        end = mid - 1