BOJ 2805 - 나무 자르기

문제

백준 온라인 저지 - 2805번

풀이 과정

나무꾼이 원하는 벌목량을 만족하는 최적의 톱날 위치를 탐색하는 문제입니다.

단순히 높이를 1씩 증가시킨다면 값의 범위가 매우 넓기 때문에 시간안에 탐색이 불가능합니다.
따라서 이분 탐색을 통해 톱날 위치를 찾아주도록 합니다.
톱날의 위치를 높일 수록 벌목하는 양이 줄어든다는 점을 이용해서 탐색을 수행하면 됩니다.

코드

import sys

N, M = list(map(int, sys.stdin.readline().split()))
trees = list(map(int, sys.stdin.readline().split()))


def possible(saw):
    temp = 0
    for tree in trees:
        if tree > saw:
            temp += (tree - saw)
    return True if temp >= M else False


def solution():
    global trees

    trees.sort()

    lo = 0
    hi = trees[-1]

    answer = 0
    while lo <= hi:
        mid = (lo + hi) // 2
        if possible(mid):
            answer = mid
            lo = mid + 1
        else:
            hi = mid - 1

    return answer


print(solution())