[BOJ] [Python] 2805번 : 나무 자르기

이진탐색을 이용하여 풀었다.

 

 

mid가 작을수록 더 많은 나무를 가져간다. 

 

num = list(map(int, input().split()))
n = num[0] # 나무 수
m = num[1] # 가져가야 할 나무 길이

tree = sorted(list(map(int, input().split()))) # 나무 길이

def BSearch(li, target):
    low = 1 # 자를 나무 최소 높이 -> 더 많이 가져감
    high = li[-1] #자를 나무 최대 높이 -> 더 조금 가져감

    result = 0

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

        tree_hap = 0

        for i in li:
            tree_hap += i - min(i, mid)

        if(tree_hap < target):
            high = mid - 1

        else:
            result = mid
            low = mid + 1

    return result


print(BSearch(tree, m))

 

이진 탐색과 관련 없는 tree_hap을 구하는 부분은, 따로 함수를 만들어서 처리해도 좋을 것 같다.