[백준 2805] 나무 자르기 (Javascript)

👩🏻‍💻문제링크

[백준 2805] 나무 자르기 (Javascript)

✍️Idea Sketch

2021-07-19

1. 로직 : 이분 탐색

• input 정렬
• 절단기에 설정할 수 있는 높이의
  • 최솟값 : left = 0;
  • 최댓값 : right = input[input.length-1]; // 마지막 원소이자 가장 큰 원소
• mid로 절단기 설정했을 때, 몇미터의 나무를 가져갈 수 있는지 확인하는 함수
  • 나무가 넉넉할 경우, right = mid-1;
  • 나무가 부족할 경우, left = mid+1;

2. mid만큼 나무를 절단한다 가정했을 때, 상근이가 가져가는 나무 길이를 구하는 함수

• 가져갈 수 있는 나무 길이 > 챙길 나무 길이 --> 높이를 높여야지 --> left = mid+1;
• 가져갈 수 있는 나무 길이 < 챙길 나무 길이 --> 높이를 낮춰야지 --> right = mid-1;

while (left <= right) {
  let mid = parseInt((left + right) / 2);
  let tree = getTree(mid);
  if (tree === M) return mid;
  else if (tree > M) left = mid + 1;
  else right = mid - 1;
}

3. 가져갈 수 있는 나무 길이를 구하는 함수 --> reduce() 사용

function getTree (mid) {
  let sum = input.reduce((a, b) => {
    if (b > mid) return a+b-mid;
    return a;
  }, 0);
  return sum;
}

4. 반례 확인 링크

• 반드시 딱 M만큼만 챙겨갈 수는 없다. M보다 더 많이 챙겨야하는 테스트케이스가 존재한다.

2 11
10 10

• 답 : 4

✍️소스코드

2021-07-19 통과

const fs = require('fs');
const stdin = (process.platform === 'linux'
  ? fs.readFileSync('/dev/stdin').toString()
  : `5 20
4 42 40 26 46`
).split('\n');
 
let [N, M] = stdin[0].split(' ').map(Number);
let input = stdin[1].split(' ').map(Number).sort((a, b) => a-b);
 
 
function getTree (mid) {
  let sum = input.reduce((a, b) => {
    if (b > mid) return a+b-mid;
    return a;
  }, 0);
  return sum;
}
 
// 본론
let left = 0, right = input[input.length - 1];
let result = 0;
 
while (left <= right) {
  let mid = parseInt((left + right) / 2);
  let tree = getTree(mid);
  if (tree === M) {
    result = mid;
    break;
  }
  else if (tree > M) {
    if (result < mid) result = mid;  // 반례 
    left = mid + 1;
  }
  else right = mid - 1;
}
 
console.log(result);