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

문제

문제 링크

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다
둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다.

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력하는 문제다.

해결 방안

백준 1654 링크!!

이번에도 이분탐색을 활용했다!!
이분탐색에 대한 설명은 위 1654번 문제에서 자세히 했으니 생략😋

코드

import sys

n, m = map(int, sys.stdin.readline().split())

tree = list(map(int, input().split()))

front = 1
rear = max(tree)

while front <= rear:
    mid = (front + rear) // 2
    total = 0

    for i in tree:
        if i > mid:
            total += i - mid
        if total > m:		#시간초과를 방지하기 위해 중간에 멈춤	
            break

    if total >= m:
        front = mid + 1
    else:
        rear = mid - 1

print(rear)

---

처음에 이분탐색으로 풀었는데도 시간초과 오류가 나와서 정말 당황했던 문제다.
위 코드에서 주석이 있는 조건문을 추가하니 다행히 100점이 나왔다.

약간 당황하긴 했지만 그래도 실버2 문제를 나름 금방 풀어서 뭔가 파이썬 고수가 된 느낌??😊😊😊😊