[Python] 나무 자르기 - 백준 (이진탐색)

해당 글은 백준 2805번 문제 '나무 자르기'를 다룬다.

문제

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

2805번: 나무 자르기

 

설명

해당 문제는 나무의 길이가 1부터 20억까지의 정수이므로 이를 완전탐색하기엔 시간이 너무 오래 걸린다.

그래서 너무 큰 수를 보면 이진탐색으로 풀어야 시간을 O(logN)으로 줄일 수 있다.

그리고 while문 안에 for문은 sum1이 m이상이 되면 break를 해주어야 시간초과되지 않을 수 있다.

 

코드

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
tree = list(map(int, input().split()))

start = 0
end = max(tree)
result = 0
while start <= end:
    mid = (start+end)//2
    sum1 = 0
    for i in range(n):
        if tree[i] > mid:
            sum1 += (tree[i]-mid)
            if sum1 >= m:
                break
    if sum1 >= m:
        result = mid
        start = mid+1
    else:
        end = mid-1

print(result)