python 백준 2110번 공유기 설치

1. 처음에 접근 방식은 공유기를 설치하여 더 넓은쪽으로 이진탐색하여 설치하는 방향으로 했었는데

반례가 무조건 생기며 잘못된 접근이라고 판단하는게 늦어졌다.

import sys


home_num, wifi = map(int,sys.stdin.readline().split())
home_loca = []
for x in range(home_num):
    location = int(input())
    home_loca.append(location)
home_loca.sort()
start = home_loca[0]
left = 1
end = home_loca[-1]-home_loca[0]
maximam = 0
result = 0
while left<=end:
    if wifi == 2:
        print(home_loca[-1]-home_loca[0])
        break
    length = (left + end)//2
    count = 1
    start = home_loca[0]
    for homes in range(home_num):
        if start + length <= home_loca[homes]:
            count += 1
            start = home_loca[homes]
    if wifi > count:
        end = length - 1
    elif wifi <= count:
        left = length + 1
        result = length
print(result)

2. 때문에 깨달은게 이진탐색을 해야된다는건 선형탐색으로 완전탐색이 가능할 수 있어야 된다는 것을 깨닫고

선형탐색으로 1m씩 거리를 줄이는 방식으로 공유기의 수를 카운트 하는 방식으로 작성하였다

import sys

def binary(start,end,target):
    global namu
    
    while(end>=start):
        mid = (start+end)//2
        answer = 0
        for x in namu_arr:
            if x>mid:
                answer += (x-mid)
        if answer >= target:
            start = mid + 1
        else:
            end = mid -1
    print(end)



namu,target = map(int,sys.stdin.readline().split())
namu_arr = list(map(int,sys.stdin.readline().split()))
start_h = max(namu_arr)
binary(1,start_h,target)