[백준] 2805 나무자르기 python

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

2805번: 나무 자르기

이분탐색 문제이다.

높이를 오름차순으로 정렬하고 시작점은 0, 끝점은 가장 큰 값(정렬했으므로 마지막 값)으로 설정해서 이분탐색을 한다.

합이 M보다 작거나 같을때는 최솟값을 올리고, 작을때는 최댓값을 내려서 탐색한다.

이때 합도 이분탐색으로 찾는데 처음에 누적합을 구하고, 처음으로 목표값 보다 커지는 인덱스를 찾으면 해당 구간에서의 합을 쉽게 구할수 있다.

 

 

 

# import sys; input = sys.stdin.readline

def binary_search_idx(s ,e, trees, goal):
    while s < e:
        m = (s + e) // 2
        if trees[m] == goal:
            return m
        elif trees[m] < goal:
            s = m + 1
        else: # trees[m] > goal
            e = m
    return s

def binary_search(s, e, goal, trees, cumul_sum):
    while s <= e:
        m = (s + e) // 2

        # 1 find a initial height, which is upper value of m
        idx = binary_search_idx(0, len(trees) - 1, trees, m)

        # 2 search cumul_sum of the section over value of m
        tmp_goal = cumul_sum[-1] - cumul_sum[idx] 
        
        # 3 cumul_sum - m * len(the section)
        tmp_goal -= m * (len(cumul_sum) - idx - 1)

        # 4 binary search again
        if tmp_goal >= goal:
            s = m + 1
        else:
            e = m - 1
    
    return e

def main():
    N, M = map(int, input().split())
    trees = sorted(map(int, input().split()))
    cumul_sum = [0 for _ in range(N + 1)]
    for i in range(1, N + 1):
        cumul_sum[i] = cumul_sum[i - 1] + trees[i - 1]
    
    ret = binary_search(0, trees[N-1], M, trees, cumul_sum)
    print(ret)


if __name__ == "__main__":
    main()