[백준 알고리즘] Node.js 15810. 풍선 공장

1. 문제

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

15810번: 풍선 공장

 

2. 풀이

• 이분탐색(Binary Search)를 이용하여 푸는 문제이다.

const [N, M, ...staff] = require('fs').readFileSync('/dev/stdin')
						.toString().trim().split(/\s/).map(v => +v);

// 풍선의 수가 만들어야 되는 M 개 보다 많은 지 확인하는 함수.
const isPossible = (time) => {
  let balloon = 0;
  for(let i = 0; i < N; i++){
    balloon += parseInt(time / staff[i]);
  }

  if(balloon >= M) return true;
  
  return false;
}

let low = 0; // 시작점
let high = M * Math.min.apply(null, staff); // 끝점, 가장 적게 많드는 스태프가 모두 만들었다고 가정.
let result = 0;

while(low <= high){
  let mid = parseInt((low + high) / 2);
  if(isPossible(mid)) {
    high = mid - 1;
    result = mid;
  } else {
    low = mid+1;
  }
}

console.log(result)

 

3. 정리

• 처음엔 반복문으로 작성하여 시간 초과 당했다. binary search를 사용해서 푸는 문제였는데, 익숙하지 않아서 구현하는데 오랜 시간이 걸렸다. 이 부분을 더 공부해봐야할 듯!
• high 변수는 다른 분의 블로그를 보고 가져왔다!

 

4. 참고

• High 변수 참고사이트
• 구현에 도움을 준 Python 코드 사이트