코딩연습

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

니 뽀 2023. 9. 1. 10:46

1. 문제

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

 

15810번: 풍선 공장

1, 2, 3번 스태프가 각각 5분, 7분, 3분씩 걸린다면 3분이 지났을 때 3번 스태프가 1개, 5분에 1번 스태프가 1개, 6분에 3번 스태프가 1개를, 7분에 2번 스태프가 1개를, 9분에 3번 스태프가 1개를, 10분에

www.acmicpc.net

 

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. 참고