백준-2805-나무 자르기

문제

나무 자르기

풀이

1. 문제조건 해석

   M만큼의 나무를 잘라내는 절단기 높이의 최댓값을 구해야 한다.

   나무의 높이 범위가 굉장히 크므로(2,000,000,000) 순차 탐색으로는 해결이 힘들어 보인다.

   따라서 이분 탐색으로 절단기의 최댓값을 찾아나간다

2. 알고리즘

   1. 최소=0, 최대=나무의 최대값 으로 초기 설정해서 이분탐색해 나간다
   2. 절단기로 가져가는 총 나무의 길이 계산
   3. • 가져가는 나무가 더 많다면
        • 절단기 높이 저장 후
        • 절단기 높이 큰 값으로 이분탐색 반복
      • 가져가는 나무가 더 적다면
        • 잘단기 높이 작은 값으로 이분탐색 반복

3. 코드

n, m = [int(_) for _ in input().split()]
trees = [int(_) for _ in input().split()]

right = max(trees)
left = 0

while left < right:
    mid = (left + right) // 2
    # 절단기로 자른 나무의 합을 구한다
    # 모든 나무에 대해 순회하므로 비효율적
    res = sum(map(lambda x:x-mid if x-mid >0 else 0 , trees)) 
    if res >= m:
        answer = mid
    if res == m:
        break
    elif res < m:
        right = mid
    else:
        left = mid + 1 # `+1`중요! 무한루프 빠지지 않게 한다

print(answer)

1. 배운점

   • 이분 탐색은 답이 정해져있는 경우,
     • ex) 집에 필요한 나무를 항상 가져갈 수 있다
   • 범위가 큰 경우

   적용해보기 좋은 알고리즘

   모든 나무에 대해 순회하면 비효율적이므로

   • 초기에 나무를 역순으로 정렬 후,
   • (나무의 높이-절단기 높이) 가 양수인 경우까지만 계산하면 효율적이다
   • 참고 블로그