백준 2805번: 나무 자르기 (JAVA)

 

문제 해석

 

M미터의 나무가 필요하다. 높이 H를 지정하면 톱날이 H만큼 상승하고 

자른 이후 (자르는 나무의 높이) - H 만큼의 나무를 얻을 수 있다. 필요 이상으로 얻지 않기 위해 M을 얻을 수 있게 하는 H 중 가장 큰 값을 최종 결과로 여긴다.

 

알고리즘

 

H를 나무들 중 가장 큰 높이로 지정한 후 원하는 결과가 나올 때까지 H를 줄여가며 원하는 결과가 나오면 반복을 종료하여

M만큼 얻을 수 있는 H의 최대 높이를 구하고자 하였다.

 

허나 다음과 같이 구현시 시간초과가 발생하였다. 따라서 결과를 좀 더 빨리 찾을 수 있도록 이분 탐색을 활용하였다.

min은 0, max는 전과 같이 나무들 중 가장 큰 높이로 지정한다.

자르는 높이를 최소와 최대의 중간으로 하고 최소가 최대를 넘어서기 전까지 반복해서 자른다.

얻은 나무들의 총합이 필요한 나무의 개수보다 적으면 max를 줄여주고

보다 크거나 같으면 더 친환경적인 값을 찾을 수 있도록 min을 높여준다.

 

코드