백준 2805. 나무 자르기

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

1. 처음의 시간초과 풀이

n, k = map(int,input().split())
arr = sorted(list(map(int,input().split())))
ans = 0
m = (arr[0] + arr[-1]) // 2

while True:
    wood = 0
    for i in arr:
        if i > m:
            wood += (i - m)

    if wood > k:
        m += 1

    if wood == k:
        ans = m
        break

print(ans)

2. 이분탐색 풀이

n, target = map(int,input().split())
arr = list(map(int,input().split()))

s = 0
e = max(arr)

while s <= e: # 두 포인터가 교차할 때 멈춤
    m = (s+e) // 2

    wood = 0
    for w in arr:
        if w > m:
            wood += (w - m)

    if wood >= target: # 조건을 만족했으면?
        s = m + 1
    else:
        e = m - 1

print(e)