백준 2805번 나무 자르기

< 백준 2805번 나무 자르기 - 마포 코딩박 >

사용한 알고리즘: 투포인터, 이분탐색


 N개의 나무의 높이와 원하는 나무길이 M 이 주어진다. 각 나무를 h 의 높이로 잘랐을 때 얻을 수 있는 나무길이는 해당나무높이 - h 이다. N개의 나무에서 얻을 수 있는 나무길이가 M 이상을 만족하는 h 의 최댓값을 구하는 문제이다.

문제풀이는 다음과 같다.
(1) (코드: 15,16)
 lo = 0, hi = Infimum 초기값을 설정 한다.

(2) (코드: 18~29)
 mid=(lo+hi)/2 라고 설정한 뒤, mid 높이로 잘랐을 때 얻을 수 있는 총 나무길이를 sum 이라 하자. 원하는 나무길이 M에 대해
 1. sum>=M 일때 lo = mid 로 높여준다.
 2. sum < M 일때 hi = mid 로 낮춰준다.
 lo + 1 < hi 일때 위 과정을 반복하고, 과정이 끝나면 구해진 lo값이 답이다.