[백준] 2805 나무 자르기 Python

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

1차시도
import sys

input = sys.stdin.readline

tree_cnt, meter = map(int, input().split())
trees = list(map(int, input().split()))
cutter = max(trees)
wood = 0

while wood < meter:
    wood = 0
    cutter -= 1
    for tree in trees:
        if cutter < tree:
            wood += tree - cutter


print(cutter)


2차시도
import sys

input = sys.stdin.readline

tree_cnt, meter = map(int, input().split())
trees = list(map(int, input().split()))
cutter = max(trees)
trees.sort(reverse=True)
wood = 0

while wood < meter:
    wood = 0
    cutter -= 1
    for tree in trees:
        if cutter < tree:
            wood += tree - cutter
        else:
            break


print(cutter)


3차시도
import sys

input = sys.stdin.readline

tree_cnt, meter = map(int, input().split())
trees = list(map(int, input().split()))
trees.sort(reverse=True)

low = 0
high = max(trees)

while low < high:
    mid = (low + high)//2

    wood = 0

    for tree in trees:
        if tree > mid:
            wood += tree - mid

    if wood < meter:
        high = mid
    else:
        low = mid + 1


cutter = low - 1
print(cutter)

알고리즘은 쉽게 작성할 수 있었지만 배열의 크기와 나무길이의 크기가 너무 커서 시간 초과가 나와서 선형탐색 그리고 선형탐색을 끝까지하지않고 찾다 이분탐색을 통해 문제를 해결했다 저번에 풀었던 문제는 index를 이용하여 푸는 문제가 있었는데 index방법을 사용하면 더 빠르게 문제를 해결할 수 있었습니다
위 코드는 cutter 절단기를 이분탐색한 방법으로 처음에는 가장큰 나무와 0 사이에 값으로 부터 시작하여 값이 작게 나오면 low값을 높게 올리고 값이 높으면 high값을 Mid값과 대칭시켜 값을 조정하는 방식으로 작성되었습니다