https://www.acmicpc.net/problem/2805
간단한 이분탐색 문제이다. 나무를 잘라서 필요한 만큼 집에 가져가는데 나무 절단기의 높이가 최대가 되는 값을 찾아야한다.우선 주어진 나무들의 높이를 정렬한다. 절단기의 높이의 최솟값을 0, 절단기의 최대값을 정렬된 나무에서 가장 큰 길이로 설정한다. 이제 우리는 절단기의 높이를 최솟값 + 최대값 / 2 해주면서 조절한다. 만약 설정된 높이의 절단기로 나무들을 잘랐을 때 잘려진 나무들의 길이의 합이 주어진 M 미터(집으로 가져가려는 나무의 길이)보다 크거나 같으면 M미터 만큼 나무를 집에 가져갈 수 있게된다. 여기서 끝이아니라 M미터의 나무도 가져갈 수 있고 절단기에 설정된 절단 높이가 최대여야한다.
if sum(cutting_tree_len) >= M:
answer = max(answer, cut_t)
left_t = cut_t
else:
right_t = cut_t위코드는 커팅된 나무들의 길이 함 >= M일 경우 절단기에 설정된 길이를 확인하여 정답에 최대값을 갱신하고 현재 절단기의 최소 기준치를 현재 절단기에 설정된 값으로 갱신해준다. 만약 M보다 작다면 절단기의 최대 기준치를 현재 절단기에 설정된 값으로 갱신해준다.
N, M = map(int, input().split())
trees = list(map(int,input().split()))
trees.sort()
left_t = 0
right_t = trees[-1]
answer = 0
while left_t+1<right_t:
cut_t = (left_t+right_t)//2
cutting_tree_len = []
for idx in range(N):
tmp_tree_len = trees[idx] - cut_t
if tmp_tree_len <= 0:
tmp_tree_len = 0
cutting_tree_len.append(tmp_tree_len)
if sum(cutting_tree_len) >= M:
answer = max(answer, cut_t)
left_t = cut_t
else:
right_t = cut_t
print(answer)