2022.02.25 [백준] (python 파이썬) 나무 자르기

 

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

2805번: 나무 자르기

---

풀이

이 문제에서 필요한 나무를 가져가기 위한 절단기의 높이를 완전탐색으로 모두 확인하면 시간초과가 발생할 것이다.

그래서 이분탐색을 이용하여 코드를 작성했다. 

우선 이분탐색을 할 범위를 정해줘야한다. 그래서 시작점을 0, 끝점을 입력받은 나무 중 가장 높은 나무로 설정했다.

그리고 binary_search함수를 만들어 이분탐색을 했다.

while문에서 mid값을 구하고 이 미드 값을 cnt_tree함수에 넣어 해당 mid길이로 나무를 잘랐을 때 가져갈 수 있는 나무의 길이를 구했다. 

이 때 구한 길이를 목표했던 target과 비교해서 만약 l이 target보다 크면 start를 mid+1로 설정해 절단기의 길이를 더 길게했을 때의 값을 탐색했다. 만약 l이 target보다 작으면 절단기의 길이를 줄여야 하기 때문에 end값을 mid-1로 설정해 더 작은 값을 탐색했다.

n,m=map(int,input().split())
trees=list(map(int,input().split()))
 
start=0
end=max(trees)
 
def binary_search(target, start, end):
    while start<=end:
        mid=(start+end)//2
        l=cnt_tree(mid)
        if l>=target:
            start=mid+1
        else:
            end=mid-1
    return end
 
def cnt_tree(a):
    length=0
    for i in trees:
        if a<i:
            length+=i-a
    return length
 
print(binary_search(m,start,end))