[백준2805_자바스크립트(javascript)] - 나무 자르기

🔴 문제

나무 자르기

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs.readFileSync(path).toString().trim().split('\n');
let [n, m] = inputs[0].split(' ').map(Number);
const tree = inputs[1].split(' ').map(Number);

let left = 0;
let right = Math.max(...tree);
let ans = 0;

while (left <= right) {
  let mid = Math.floor((left + right) / 2);
  let sum = 0;

  for (const t of tree) {
    if (t > mid) {
      sum += t - mid;
    }
  }

  if (sum >= m) {
    ans = mid;
    left = mid + 1;
  } else {
    right = mid - 1;
  }
}

console.log(ans);

🟢 풀이

⏰ 소요한 시간 : -

처음에는 그냥 모든 경우의수를 확인해주도록 풀이했는데 시간초과가 발생했다.

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs.readFileSync(path).toString().trim().split('\n');
let [n, m] = inputs[0].split(' ').map(Number);
const tree = inputs[1]
  .split(' ')
  .map(Number)
  .sort((a, b) => b - a);

let ans = tree[0];
while (true) {
  let sum = 0;
  for (const t of tree) {
    if (t > ans) sum += t - ans;
  }
  if (sum >= m) break;
  ans -= 1;
}
console.log(ans);

위 코드의 경우 while에서 ans값을 감소시키면서 for문내부의 tree를 다 돌기 때문에 시간복잡도는 트리의 최대값 * 트리의 개수가 된다.
트리의 최대값이 2,000,000,000이므로 시간초과가 발생하여 이분탐색으로 풀이를 해야한다.

따라서 이분탐색으로 풀이하기 위해 절단기가 있을 수 있는 최소값 left와 최대값인 트리의 최대값을 찾아 right에 할당한다.

이후 left가 right를 넘길때까지 수행하는데 중간값을 찾아 모든 트리를 순회하며 중간값과 트리의 오프셋을 구해 sum에 더해준다.

이 값이 목표치인 m보다 크다면 left값을 중간값 보다 1 더해주고, 아니라면 right 값보다 1을 빼준다.

🔵 Ref