백준 2805 나무자르기

문제

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

코드

n, m = map(int, input().split())

treeH = list(map(int, input().split()))+[0]
treeH.sort()

prefixSum = [0]*(n+1)
for i in range(1, n+1):
    prefixSum[i] += prefixSum[i-1]+treeH[i]


low = 0
high = treeH[n]
answer = 0
while low <= high:
    mid = (low+high)//2
    l = 0
    h = n
    index = n
    while l <= h:
        mi = (l+h)//2
        if treeH[mi] <= mid:
            l = mi+1
        else:
            index = mi
            h = mi-1
    index -= 1
    tree = prefixSum[n] - prefixSum[index]-(mid*(n-index))
    if tree >= m:
        answer = mid
        low = mid+1
    else:
        high = mid-1
print(answer)

풀이

절단기 높이값을 이분탐색으로 찾습니다
이 때 높이값에 맞춰서 잘리는 나무의 양을 누적합과 이분탐색으로 구해서 시간을 단축했습니다