해당 포스팅은 백준 2805번 나무자르기 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였다.
[첫째 줄] : 나무의 수 N, 상근이가 집으로 가져가려고 하는 나무의 길이 M
(1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)
[둘째 줄] : 나무들의 높이
나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다.
(0 <= H <= 1,000,000,000)
적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.
N과 M이 각각 10만, 20만이므로 BF로 풀면 시간 초과이다. 이분탐색으로 풀어보자.
아래 예제로 설명을 하겠다.
4 7
20 15 10 17
input의 첫 번째 줄은 NM, 두 번째 줄은 trees로 설정하자.
4
7
[20, 15, 10, 17]
[10, 15, 17, 20]
binarySearch
를 구현한다.Math.floor((start + end) / 2)
로 절단기의 위치이다.if
총합이 M보다 클 시, mid >= answer
라면 업데이트를 해준다(그 이유는 높이의 최댓값
을 구하므로 이분탐색으로 업데이트해주어야 한다).mid + 1
로 옮겨준다.else
총합이 M보다 작을 시, 나무가 부족한 것이므로 절단기 높이를 낮추기 위해 end를 mid - 1
로 옮겨준다.binarySearch(trees, M, 0, trees[trees.length - 1])
const input = require('fs').readFileSync('/dev/stdin').toString().split('\n');
const [NM, trees] = input.map((el) => el.split(" ").map((val) => +val));
const [N, M] = NM;
trees.sort((a,b) => a-b);
function binarySearch(arr, M, start, end) {
let answer = Number.MIN_SAFE_INTEGER;
while(start <= end) {
let mid = Math.floor((start+end) / 2);
let sumTree = arr.reduce((prev, curr) =>{
let cutTree = curr - mid;
return prev = (cutTree > 0) && (prev + cutTree)
}, 0);
if (sumTree >= M) {
if (mid > answer) answer = mid;
start = mid + 1;
}
else {
end = mid - 1;
}
}
return answer;
}
console.log(binarySearch(trees, M, 0, trees[trees.length - 1]));