이진탐색 [백준] 2805. 나무 자르기

문제링크

초기 풀이

tree, wood = map(int, input().split(' '))
tree_list = list(map(int, input().split(' ')))


tree_list.sort()
wood_count = 0
height_list = [i for i in range(tree_list[-1])]
left_idx = 0
right_idx = tree_list[-1]

while True:
    wood_count = 0
    height = (right_idx+left_idx)//2
    for i in range(len(tree_list)-1, -1, -1):
        if height > tree_list[i]:
            break
        else:
            wood_count += tree_list[i]-height
    if wood_count < wood:
        right_idx = height
        #print('left_idx is ', left_idx, 'right_idx is ', right_idx)
    elif wood_count > wood:
        left_idx = height
        #print('left_idx is ', left_idx, 'right_idx is ', right_idx)
    else:
        print(height)
        break

될 수 있는 정답을 height_list 로 만들고 heigt마다 문제에서 요구하는 정답이 맞는지 판별하고 아닐 시에 height_list의 인덱스 가짓수를 반으로 줄여가기 위하여 만들었는데, 아무대로 정답 판별식이 구린가부다,,

정답

tree, wood = map(int, input().split(' '))
tree_list = list(map(int, input().split(' ')))
left_idx = 1
right_idx = max(tree_list)-1

while right_idx >= left_idx:
    wood_count = 0
    height = (right_idx+left_idx)//2
    for i in tree_list:
        if height < i:
            wood_count += i-height
    #print('wood_count is', wood_count)
    if wood_count < wood:
        right_idx = height-1
        #print('left_idx is ', left_idx, 'right_idx is ', right_idx)
    else:
        left_idx = height+1
        #print('left_idx is ', left_idx, 'right_idx is ', right_idx)
print(right_idx)

판별식이 아닌 list sorting이 시간을 많이 잡아먹는 것으로 보인다.
이에 더해 이분 탐색도
height가 해당안되면
right_idx를 -1,
height가 해당되거나 값을 더 키워야 되면 left_idx를 +1 해주고,
left_idx가 right_idx를 넘어서면
right_idx를 반환해준다

5 20
4 42 40 26 46

left_idx is 24 right_idx is 45
left_idx is 35 right_idx is 45
left_idx is 35 right_idx is 39
left_idx is 35 right_idx is 36
left_idx is 36 right_idx is 36
left_idx is 37 right_idx is 36
36