simm4256   4년 전

알고리즘은 다음과 같습니다.

1. 나무를 오름차순 정렬합니다.

2. 0~x번 나무까지의 합을 sum[x]에 저장합니다.

3. 0~n-1번까지 탐색, i번 나무의 높이로 잘랐을 때 구할 수 있는 나무의 길이가 m보다 큰지를 판별합니다.

이 때 구해진 나무의 총합은, i+1 ~ n-1 번 나무까지의 길이의 총합에서 h[i]*(n-i-1)을 뺀 값과 같습니다.

  3-1) i번 나무의 높이로 잘랐을 때, 구해진 나무의 총합이 m보다 크면 다음 나무로 넘어갑니다.

  3-2) 그렇지 않다면, 탐색을 종료합니다.


4. 3번 탐색이 종료된 후 i값이 의미하는 바는, 정답은 반드시 h[i-1] ~ h[i] 사이에 존재한다는 것입니다.

  4-1) i번 나무의 높이로 잘랐을 때, 구해진 나무의 총합이 m과 같다면 정답은 h[i]입니다.

  4-2) i가 0이면, 정답은 0~h[0] 사이의 값입니다. 그런데, 이 때는 정답을 간단히 구할 수 있습니다. 

먼저, 높이를 h[0]으로 설정했을때 가져가는 나무의 길이의 총합을 구하고 이를 ss라 합니다.

이 상태에서 높이를 1 줄인다면, 나무는 총 n만큼 더 가져갈 수 있습니다.

즉, h[0] - (m-ss)/n 을 올림처리를 해주면 정답이 나옵니다.

  4-3) 그 외의 경우, 정답은 h[i-1]~h[i] 사이의 값입니다. 이 때는 높이를 이분탐색을 통해 답을 구합니다.

simm4256   4년 전

big을 설정하는 부분이 잘못됐네요.

초기값을 -1로 잡고 14줄의 if문을 big<mid 로 바꾸니 맞았습니다.


그리고 제 풀이법을 다시 생각해봤는데

이 문제 애초에 이분탐색을 할 필요도 없는 문제였네요.

4-2)의 경우에서 구한 것처럼 4-3)도 똑같이 구할 수 있습니다.

정렬하는데만 시간이 소요되게 짤 수가 있네요..

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