BaekJoon2805_나무 자르기

나무 자르기

풀이

• 이분 탐색을 사용하였다.

1. trees 리스트에 나무 높이들을 입력받음
2. 나무 높이 순대로 오름차순 정렬
3. start = 0, end에 트리 높이 들의 합 할당
4. while문의 종료조건은 start<=end
5. 첫 중간값은 (start+end)//2 로 설정
6. result = 0으로 할당하고 trees 리스트를 for문으로 돌린다.
7. trees의 각 원소들을 확인하고 중간값과 비교하여 나무의 높이가 더 크면
   result += i- mid
8. result의 값이 최소한 가지고 가야하는 값(m)보다 크거나 같으면 start = mid + 1
   그 외에는 end = mid -1
9. while문이 종료된 뒤의 end값이 답이 된다.

# 정답코드
n,m = map(int,input().split())
trees = list(map(int,input().split()))
trees.sort()
start = 0    
end = sum(trees)

while start <= end:
    mid = (start + end) // 2
    result = 0
    
    for i in trees:
        if i > mid:
            result += i - mid
        
    if result >= m:
        start = mid + 1
    else:
        end = mid - 1

print(end)