[백준/파이썬] 2805번: 나무 자르기

문제

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

풀이

• 필요한 나무 M미터
• 높이 H(0<=H) 지정 -> H미터 만큼 자름
  • H보다 큰 나무는 H 윗부분 잘림(낮은 나무는 x)
• H의 최대값

이분 탐색을 활용하여 값을 찾아가면 문제를 해결할 수 있습니다.

여기서 유의할 점은 h보다 낮은 부분은 포함을 시키지 않기 때문에 h보다 클 경우만 구해줘야 합니다.

for i in tree:
    if i > mid: # 배열에 있는 나무의 길이가 mid보다 클 경우만 cnt에 추가
        cnt += i - mid

코드

import sys
input = sys.stdin.readline

n,m = map(int,input().split())
tree = list(map(int,input().split()))
l,r = 1, max(tree)

while l <= r:
    mid = (l+r) // 2
    cnt = 0
    for i in tree:
        if i > mid:
            cnt += i - mid
    if cnt >= m:
        l = mid + 1
    else:
        r = mid - 1

print(r)