[JS][백준]1166_선물

문제 번호

1166번: 선물

 

 

알고리즘 분류

• 이분 탐색

 

문제 풀이

 문제를 보자마자 A를 이분 탐색으로 구해야겠구나 싶었다. 근데 A가 정수단위가 아니었다. 그래서 고민을 좀 해봤는데 문제에서 오차는 10^-9까지 허용한다고 되어있다. 그래서 이분 탐색을 진행하되, end - start가 오차보다 작을 때까지만 진행하면 되겠다는 생각이 들었다.

 

function binarySearch() {
  let ret = 0;

  let left = 0;
  let right = Math.max(L, Math.max(W, H));
  for(let i=0; i<57; i++) {
    let mid = (left + right) / 2;    
    if (check(mid)) {
      left = mid;
      ret = mid;
    } else {
      right = mid;
    }
  }
  return ret.toFixed(9);
}

 문제에서 주어진 직육면체의 최대 길이는 1,000,000,000 인데, 이걸 계속 반으로 나누다 보면 56번째쯤에 end-start가 오차범위보다 작아진다.(for문으로 돌려봤는데 56번째인가 57번째 인가 그랬음, 넉넉하게 10000 정도로 잡아도 문제를 푸는 데는 지장이 없다.) 보통의 이진 탐색에서는 left = mid+1 // right = mid -1 이런 식으로 left와 right가 언젠가 만나지만, 이 문제에서는 left = mid // right = mid 이기 때문에 for문이나 어떠한 조건을 사용하여 멈춰주지 않는다면 무한루프에 빠지게 된다.

 

 아무튼 이렇게 구한 mid이 A 가 될텐데, A*A*A가 L*W*H 안에 들어갈 수 있는지 확인해보자.

function check(a) {
  if (Math.floor(L / a) * Math.floor(W / a) * Math.floor(H / a) >= N)
    return true;
  return false;
}

 

전체 코드

const input = require('fs').readFileSync('dev/stdin').toString().trim().split(' ').map(Number);
const [N, L, W, H] = input;

function check(a) {
  if (Math.floor(L / a) * Math.floor(W / a) * Math.floor(H / a) >= N)
    return true;
  return false;
}

function binarySearch() {
  let ret = 0;

  let left = 0;
  let right = Math.max(L, Math.max(W, H));
  for(let i=0; i<57; i++) {
    let mid = (left + right) / 2;    
    if (check(mid)) {
      left = mid;
      ret = mid;
    } else {
      right = mid;
    }
  }
  return ret.toFixed(9);
}
function main() {
  let answer = binarySearch();
  return console.log(answer);
}
main();

특이사항