[이분탐색] 백준 #2805 나무 자르기 - Python

🗂️ 문제

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

 

💡 접근법

N과 M의 범위가 크기 때문에 모든 경우의 수를 계산할 경우 시간초과가 발생한다.

 

절단 높이를 작게하면 가져가는 나무의 길이가 크고, 절단 높이를 크게하면 가져가는 나무 길이기 작다.

이를 이용하여 절단 높이를 기준으로 이분 탐색을 수행한다.

 

또한 절단 높이를 최대로 하여 필요한 만큼의 나무를 가져가므로, 나무의 길이가 딱 떨어지지 않는 경우를 생각해야 한다. 이 경우엔 high(mid-1) 값을 출력하면 필요한 만큼 나무를 가져가면서 최대로 하는 절단 높이를 구할 수있다.

 

😎 내 코드

import sys

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

def cal_tree(height):
    sum = 0
    for t in tree:
        if t-height > 0:
            sum += t - height
    return sum

low = 0
high = max(tree)
while (low <= high):
    mid = (low+high) // 2 # 절단 높이
    tree_height = cal_tree(mid) # 가져가는 나무 길이

    if tree_height == M:
        print(mid)
        break
    else:
        if tree_height < M:
            high = mid - 1
        elif tree_height > M:
            low = mid + 1

if low > high:  # 나무 길이기 딱 떨어지지 않는 경우
    print(high)

 

✅ 정답 확인