(파이썬) 백준 2805번 "나무 자르기"

---

# 답

N, M = map(int, input().split())
tree = list(map(int, input().split()))
lo = 0
hi = max(tree)
mid = (lo + hi) // 2

def get_total_tree(h):
    ret = 0
    for t in tree:
        if t > h:
            ret += t - h

    return ret

ans = 0
while lo <= hi:
    if get_total_tree(mid) >= M:
        ans = mid
        lo = mid + 1
    else:
        hi = mid - 1

    mid = (lo + hi) // 2

print(ans)

 

 

 

 

---

# 분석

절단기 높이의 '최댓값'을 구하는 최적화 문제인데 결정 문제로 바꿔서 풀 수 있으므로 파라메트릭 서치로 풀면 됩니다.

절단기 높이가 h라면, 나무들을 자른 길이를 구할 수 있고 그 합이 M 이상이라면 h는 정답 후보가 됩니다.

 

1) h가 정답 후보라면 더 큰 h가 있는지 살펴봐야합니다.

2) h가 정답 후보가 아니라면 h를 더 줄여야 됩니다.

(h가 클수록 가져갈 수 있는 나무 양이 줄어들고, h가 작을수록 나무 양이 증가합니다.)

 

이를 반복하여 h의 최댓값을 찾습니다.