백준 2805번 나무 자르기 - Python

문제 링크 : https://www.acmicpc.net/problem/2805

이 문제는 이분탐색을 이용하여 푸는 문제이다.
나는 처음에 이분탐색의 개념을 몰라서 구글링하고 강의를 들으며 개념부터 이해했다.

만약 이 문제를 풀려고 할 때, 이분탐색이 무엇인지 모른다면 개념부터 이해하고 오자.

이분탐색

탐색 기법중에 하나로 원하는 탐색범위를 두 부분으로 분할해서 찾는 방식이다. 그렇기에 원래의 전부를 탐색하는 탐색 속도에 비해 빠르다는 장점이 있다. 이분 탐색을 하는 방법은 left , right , mid 값으로 탐색하는 것이다. mid의 값은 (left + right)/2 으로 잡아주고 우리가 검색하고자 하는 값과 mid 값을 비교한다.

풀이

1. 필요한 나무 길이만큼 최소한으로 잘라야한다.
2. 최소한의 자를 수 있는 길이 (=1)과 최대한으로 자를 수 있는 길이(나무들 중에서 제일 큰 나무)를 시작과 끝으로 지정하고 중간값을 찾는다. 이분탐색
3. 중간값을 기준으로 나무가 더 필요하다면 중간값 -1, 나무를 필요 길이에 비해 너무 많이 잘랐다면 중간값 +1을 해주어 start의 기준을 바꿔준다.

해답

n, m = map(int,input().split()) # n = 나무의 수 m = 필요한 나무의 길이
tree = list(map(int,input().split())) # 그루 당 나무의 길이 리스트

def h(m,tree) :
    start = 1
    end = max(tree) # 리스트 안의 나무에서 제일 키 큰 나무의 길이
    
    while start <= end : # start가 end보다 작아지면 범위가 []없기 때문에 끝난다.
        leng = 0 # 자른 나무 길이의 합을 담아둘 변수
        mid = (start + end) // 2 # start ~ end 의 중간값

        for i in tree :  # 일단 잘라보기
            if i >= mid :  # 중간값보다 한 그루의 나무가 길이가 크다면
                leng += i - mid # 잘라서 leng에 넣자

        if leng >= m : # leng(자른나무)가 m(필요한 나무의 길이)보다 크다면,
            start = mid + 1 # 시작점을 조정하여 범위를 줄이자 (더 높이 잘라야 덜 자를수 있기 때문)
        else : 
            end = mid - 1 # m보다 적게 잘랐다면 end 값을 줄여서 높이의 범위를 낮추자
    return end # 다 돌면 end를 변환해라.

print(h(m,tree)) # 함수를 실행하면 end만 남아 높이가 출력된다.