백준: 2805 나무 자르기

문제

2805번: 나무 자르기

 

문제 풀이

 앞서 다룬 랜선 자르기와 동일한 방식으로 풀 수 있는 문제이다. 다른 점이 있다면, 잘리는 나무가 mid보다 큰 경우만 경우에 포함된다. 문제에 주어진 것처럼 이분 탐색으로 15라는 높이로 나무를 자른다면 20 - 15 = 5, 17 - 15 = 2, 총 7m의 나무를 가져갈 수 있다.

 

코드

from sys import stdin


if __name__ == '__main__':
    k, n = map(int, stdin.readline().split())
    trees = list(map(int, stdin.readline().split()))

    s, e = 1, max(trees)

    while s <= e:
        m = (s + e) // 2
        make_tree = sum([tree - m if tree >= m else 0 for tree in trees])

        if make_tree >= n:
            s = m + 1
        else:
            e = m - 1

    print(e)