이분 탐색. [2805]

[1. 문제 설명]

일렬로 있는 각기 다른 높이의 나무를 절단기를 통해 일정 높이로 베었을 때,

얻을 수 있는 나무의 길이를 만족하는 것 중,

절단기에 설정할 수 있는 높이의 최대값.

 

 

[2. 풀이 접근]

나무를 베어 얻을 수 있는 나무의 길이는 범위는 다음과 같다.

[1, MaxTree]

여기서 MaxTree 는 나무의 최대 높이

 

이 범위 내에서 절단기에 설정 할 수 있는 높이를 결정해야 한다.

나무의 최대 높이는 10억 정도 되므로,

순차 탐색으로는 시간 내에 해결 할 수 없으므로, 이분 탐색을 적용한다.

 

일부 나무는 탐색 중 적용 할 높이 보다 작은 것 이 있으므로,

얻은 나무 길이가 0 이하의 값은 얻을 수 있는 것에서 제외해야 한다.

 

 

[3. 코드]