[백준] 2805번 나무 자르기

나무를 왜자르니 얘들아..

 

www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

암튼 나무를 자르는걸... 돕기로합니다

 

🏃‍♀️작성한 코드

# 2805 번 : 나무 자르기
def binary_search_2805():
  n, m = map(int, input().split())
  trees = list(map(int, input().split()))

  # n = 4
  # m = 7
  # trees = [20, 15, 10, 17]

  s = 0
  e = max(trees)
  answer = 0

  while s <= e :
    c = (s+e) // 2
    # print('s,e,c====', s,e,c)

    hap = 0
    for t in trees:
      if t >= c:
        tmp = t - c
        hap += tmp
        # print('tmp, hap', tmp, hap)
    
    if hap < m : #길이가 모자람
      e = c - 1
    elif hap >= m : #길이가 넘침
      s = c + 1
      answer = c 
  print(answer)

 

일단 s,c,e는 다음과 같다(start, center, end의 약자...)

그래서 가져가는 나무의 합(hap)이 내가 필요한 길이 m보다 작으면(모자라면)

e = c -1 로 변경하여 H를 내린다.  -> 나무를 더 자르게 됨

 

hap이 m보다 크다면 (필요한 길이보다 많이 자름) 

s = c+1 로 변경하여 H를 올린다. ->나무를 덜 자르게 됨

 

이를 반복하면서 적절한 길이를 찾는다.