20210619 알고리즘 문제 풀이

백준 2805번 나무 자르기

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

N,M = map(int,input().split())
tree = list(map(int,input().split()))


def treeSum(height):
    Sum = 0
    for i in tree:
        if i-height >0:
            Sum += (i-height)

    return Sum

def binarySearch(target):
    start,end=0, max(tree)
    ans = 0
    while(start<=end):
        mid = (start+end)//2
        Sum = treeSum(mid)
        if Sum < target :
            end = mid -1
        if Sum >= target:
            ans = mid
            start = mid + 1

    return ans

print(binarySearch(M))

풀이

• 톱날의 높이가 낮을수록 더 많은 나무를 벨 수 있다
• 이진탐색 이용
• 톱날의 높이가 결정되었을 때, M미터보다 크거나 같으면, 톱날의 높이 H를 높여준다
  (같을 때 톱날의 높이를 높여줘야함)
• M미터보다 작으면 톱날의 높이 H를 낮춰준다
• 나무의 높이가 톱날의 높이보다 높은 경우에만 나무를 가져갈 수 있다
• 따라서 그런 경우에, sum += 나무 높이 - 톱의 높이 = tree[i] - height로 계산한다
• 결과를 return