Week 01 ~ 04 : 알고리즘 문제 풀이

파이썬 백준 2805 나무 자르기

정글러 2021. 11. 11. 16:38
n, m = map(int, input().split())
T = list(map(int, input().split()))

def Bsearch(list, goal, lower, upper) :
    if lower > upper :
        return upper
    sum = 0
    center = (lower + upper) // 2
    for i in list :
        if i > center :
            sum = sum + i - center
    if sum == goal :
        return center
    if sum > goal :
        return Bsearch(list, goal, center + 1, upper)
    else :
        return Bsearch(list, goal, lower, center -1)

print(Bsearch(T, m, 0, 1000000000))

나무를 자르는데 왜 이분탐색인가 싶었는데 어떻게 나무 높이가 1,000,000,000미터...

range의 중앙값을 일단 찔러보고 결과에 따라 위아래로 upper, lower bound를 좁혀가는 이분 탐색을 구현했다.

범위를 좁히다가 lower가 upper보다 큰 모순상황이 되면 upper( = 이전 재귀단계의 center)를 리턴

혹은 운좋게 찔러본 center 값이 맞으면 center를 리턴

 

나무 높이의 range는 10억인데 나무가 담긴 리스트 T의 길이는 1,000,000이다.

길이 1,000,000 리스트에서 max값 찾아 upper에 10억 대신 넣기 vs 그냥 10억부터 시작하기

리스트를 뒤져 max값을 뽑아도 그게 10억과 크게 차이나지 않으면 시간단축이 안될거라 판단해서

그냥 upper 시작값에 10억을 넣었다. 어차피 절반씩 금방 줄어들텐데.