[Python] 2805번 나무 자르기

✏️ 문제

 

문제 파악

이분 탐색을 사용해야 하는 거의 대표적인 문제!!!!!

이분 탐색을 안 사용하면 보통.. 아니 대개 "시간 초과" 가 뜬다... ^^

 

알고리즘

• 이분 탐색
• 매개 변수 탐색

 

코드

n, m = map(int, input().split())  
trees = list(map(int, input().split()))  

def binary_search(trees, target):
  left, right = 0, max(trees)

  while left <= right:
    mid = (left + right) // 2
    total = 0
    
    for h in trees: 
      if h > mid:
        total += h - mid

    if total < target:
      right = mid - 1
    else:
      left = mid + 1

  return right

print(binary_search(trees, m))

 

 

 

 

---

⭐️ 이분 / 이진 탐색에 대해 잘 모른다면?

[알고리즘] 이분 / 이진 탐색 (Binary Search) 알고리즘