[백준 알고리즘] Node.js 2805. 나무 자르기

1. 문제

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

 

2. 풀이

- 입력 첫째줄에는 나무의 수 n 과 적어도 가져가야 하는 미터의 길이인 m이 주어진다.

- 입력 둘째줄에는 나무의 높이가 주어졌다.

- 나무의 높이 중 가장 큰 값을 이용하여 이진 탐색을 이어나가도록 계획했다.

const inputs = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');
const [n,m] = inputs.shift().split(' ').map(v => +v);

// 2번째 줄 나무의 높이
const trees = inputs[0].split(' ').map(v => +v);

// 나무의 높이 중 가장 큰 값
let max = Math.max(...trees);
let min = 1;
let best = 0; // 답이 될 값

while(min <= max){
  let mid = Math.floor((max + min) / 2); // 중간 값 찾기

  let sum = 0;
  // 나무의 높이를 자르고 가져갈 값들을 더해준다.
  trees.forEach((tree) => {
    if(tree > mid) sum += (tree - mid);
  })

  // 원하는 길이보다 가져가는 나무의 길이가 더 길다면
  if(sum >= m) {
  	// 그중 가장 긴 값!
    if(mid > best) best = mid;
    min = mid + 1;
  } else { // 짧다면
    max = mid - 1;
  }
}

console.log(best)

 

3. 정리

- 이분 탐색은 기준 값들만 잘 설정하면 쉽게 풀 수 있을 것 같다.

 

* 이진 탐색(Binary Search)