[백준] 2805번 : 나무자르기

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

2805번: 나무 자르기

해당 문제는 아래의 문제에서 최소값을 구하는과정을 추가된 경우이다.

https://bigkwangs.tistory.com/38

[백준] 2110번 : 공유기 설치

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구해야 함으로 나무를 집에 가져기가위한 값을 최소값을 찾아서 그 최소값을 갖는 높이의 결과를 리턴하면 된다.

 

N, M = map(int, input().split()) # 나무의 개수, M미터의 나무를 가져가야함.

tree = list(map(int ,input().split()))
    
tree.sort() # 이분 탐색을 위해 정렬한다.

start = 1
end = tree[-1]

result = int(10e9)
ans = 0
if N == 1:
    print(tree[0] - M)
else:
    while start < end:
        mid = ( start + end ) // 2 # H값을 선정
        sum = 0
        for i in range(N):
            cost = tree[i] - mid
            if cost > 0:
                sum += cost
            
        if sum >= M: # 값이 큰경우 작은 범위로 탐색하게 한다. 높이를 늘린다.
            if result > sum:
                result = sum
                ans = mid
            start = mid+1
        else: # 값이 작은경우 큰 범위로 탐색하게 한다. 높이를 낮춘다.
            end = mid
              
    print(ans)