[Python]이분탐색 백준 2805

문제

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

M의 나무를 가져가야 할때 최악의 상황에서 최대길이에 M만큼을 뺀 길이만큼 

절단해야 한다.(높이는 최소)이값과 최대길이의 값의 중간값을 기준으로 이분탐색을 

시행해 준다.

코드로 구현해보자

import sys
 
N,M=map(int,sys.stdin.readline().split())
tree=list(map(int,sys.stdin.readline().split()))
 
max_cut=max(tree)
min_cut=max_cut-M#나무를 가장 많이 자를때
 
result=0
while min_cut<=max_cut:
    mid = (max_cut + min_cut) // 2
 
    sum_tree=0
    for i in tree:
        if i>mid:
            sum_tree+=i-mid
 
    if sum_tree>=M:#원하는 목재보다 많이 나왓으면 높이를 늘림
        result = mid
        min_cut=mid+1
    else:#원하는 목재보다 작게 나온다면 높이를 줄임
        max_cut=mid-1
 
 
print(result)

시간초과가 뜬다.

 pypy3로 제출했을때는 성공이다.

import sys
 
N,M=map(int,sys.stdin.readline().split())
tree=list(map(int,sys.stdin.readline().split()))
 
 
tree.sort(reverse=True)#내림차순정렬
max_cut=tree[0]
min_cut=max_cut-M#나무를 가장 많이 자를때
 
 
result=0
while min_cut<=max_cut:
    mid = (max_cut + min_cut) // 2
    sum_tree=0
    for i in tree:
        if i>mid:
            sum_tree+=i-mid
        else:
            break
 
    if sum_tree>=M:#원하는 목재보다 많이 나왓으면 높이를 늘림
        result = mid
        min_cut = mid + 1
    else:#원하는 목재보다 작게 나온다면 높이를 줄임
        max_cut=mid-1
 
 
print(result)

최대한 줄인다고 줄여봤지만 역시 시간초과이다.

아래는 성공한 코드인데 무슨 차이인지 모르겠다.

N,M = map(int,input().split())
tree=list(map(int,input().split()))
def treesum(height):
    Sum=0
    for i in tree:
        if i-height > 0:
            Sum+=(i-height)
    return Sum
 
def binaray(target):
    start,end=0, max(tree)
    result =0
    while(start <=end):
        mid = (start + end) // 2
        Sum = treesum(mid)
        if Sum < target :
            end = mid -1
        elif Sum >= target:
            result = mid
            start = mid+1
    return result
 
print(binaray(M))
 

어떤부분에서 차이점을 만드는지 알려주신다면 감사하겠습니다.