rktkek456   2년 전

아무리 생각해봐도 이분 탐색으로 푸는 방법은 모르겠고

제 생각 대로 풀면 시간초과나 틀렸다고 나오는데 어떻게 생각해야 이분탐색을 떠올릴수 있을까요?

힌트 부탁드립니다ㅠㅠ

jh05013   2년 전

절단기 높이를 특정 자연수 H로 고정하면 나무를 몇 미터 가져올 수 있나요?

djm03178   2년 전

자르려는 높이를 x라고 하면, 그 때 잘라내는 나무의 양을 O(N)에 구할 수 있습니다. x가 작을 수록 나무의 양이 같거나 많아지는 것이 자명하므로, 높이 x에서 구한 나무의 양이 M보다 크면 x를 키우고, M보다 작으면 x를 줄이는 방법으로 최대 O(log10억)번의 O(N)개 탐색으로 답을 구할 수 있습니다.

댓글을 작성하려면 로그인해야 합니다.