[백준] 나무 자르기

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

 

1. 문제 이해 및 해결과정

- 나무의 최대 높이는 10억 , 이진탐색으로 탐색하면 log2(10^9) 약 31번 -  나무의 수가 최대 백만이므로 나무의 높이를 바꾸면서, 바꿀때마다 모든 나무를 체크 하는 경우 31*백만 = 3000만번의 연산이 필요하다

 

 

 

2. 풀이방법

1. 이분탐색 [python]

#나무 자르기
#https://www.acmicpc.net/problem/2805
import sys
sys.stdin = open("input.txt","r")
n,m=map(int,input().split())
tree=list(map(int,input().split()))
lt=0
rt=max(tree)
res=0
def count(mid):
    sum=0
    for x in tree:
        if x-mid>0:
            sum+=(x-mid)
    return sum

while lt<=rt:
    mid=(lt+rt)//2
    sum=count(mid)
   # print(sum,mid)
    if sum >= m:
        res=mid
        lt=mid+1
    else:
        rt=mid-1
print(res)

 

3. 오답원인

 

4. 알게된 점