2805.md

백준 2805

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

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

소스코드

import sys

input = sys.stdin.readline


N, M = map(int, input().split())
trees = list(map(int, input().split()))

top = max(trees)
bottom = 0

result = 0

while bottom <= top:
    curr = (top + bottom) // 2
    total = sum([max(0, t - curr) for t in trees])

    if total >= M:
        result = curr
        bottom = curr + 1
    else:
        top = curr - 1
    
print(result)

해설

기본적인 이분 탐색 문제다.

나무를 목표치(M)보다 많이 가져가게 되면 result에 현재 값을 넣고 bottom을 올리고, 적게 가져가게 되면 top을 줄여 기존보다 더 많이 가져가도록 한다.