[백준] 파이썬 2805 : 나무 자르기

 

 

# 이분탐색. m만큼 자르는데 필요한 높이를 이분탐색으로 찾기
# 필요한 높이의 최소값은 1 최대값은 제일 높은 나무의 높이
# 나무의 높이가 중간값보다 크다면 값을 빼주고 총합을 구함.
# 총합이 m과 같다면 중간값이 결과값.

n, m = map(int, input().split())
trees = sorted(list(map(int, input().split())))
start, end = 1, max(trees) # 나무 높이를 이진 탐색하기 위해 정한 범위 
while start <= end: # 시작값이 끝값보다 작을동안 반복
    temp = 0 # 잘린 나무 길이의 총합
    mid = (start + end) // 2 # 중간값 구하기
    for i in trees:
        if i >= mid: # 나무 높이가 벌목 높이보다 높다면
            temp += i - mid # 잘라낸 길이만큼 temp에 더함
    if temp >= m: #잘라낸 길이가 m보다 크다 = 벌목 높이를 높여야함
        start = mid + 1
    else: # 잘라낸 길이가 m보다 작다 = 벌목 높이를 낮춰야함 
        end = mid - 1
print(end) # 결과 출력

 

 

 

 

 

 

 

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

2805번: 나무 자르기