백준 2805 나무 자르기

n, m = [int(v) for v in input().split()]
trees = list(map(int, input().split()))

s, e = 1, max(trees)

while s <= e:
    cut = (s+e)// 2
    cnt = 0
    for tree in trees:
        if tree > cut:
            cnt += tree - cut
    
    if cnt >= m:
        s = cut + 1
    else:
        e = cut -1
        
print(e)

주어진 n과 m의 크기가 말도 안되게 크므로 이중 for문을 돌면서 답을 찾는 방식은 불가능하고 이분탐색을 사용하여 해결해야 한다.

1과 주어진 나무 길이의 최대 값으로 start와 end값을 설정해준다.
이후 나무들을 자르면서 자를 수 있는 나무의 자른 후의 값을 저장해 나간다. 이 값이 주어진 M 값보다 크거나 같으면 start를 변경해주고 그렇지 않으면 end를 변경해 주는 것을 반복해서 값을 구해준다.