[Programmers] 입국심사 문제 - (javascript)

문제 이름 :  입국심사

---

 

<<< 문제 내용 >>>

---

function solution(n, times) {
    let answer =0;
    
    const binary_search = () => {
        let left = 1;
        let right = Math.max(...times) * n;

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

            for(let time of times){
                ppl += Math.floor(mid/time);

                if(ppl>=n) break;
            }

            if(ppl>=n){
                answer = mid;
                right = mid -1;
            }else{
                left = mid +1;
            }
        }
    }
    
    binary_search();
    
    return answer;
}

* 이분탐색을 써야 한다는 것을 알면서도 이 문제를 이렇게 바로 풀 수 있나 싶었다.

 

풀면서 느낀 점이 이런 유형을 접해보지 않았다면 수학문제처럼 접근조차 못하기 쉽지 않았을까? 했는데

다른 사람들은 어떻게 느끼는지 궁금하다..

 

이 문제는 각 심사대의 사람들이 각각 얼마의 인원을 따로따로 받을 수 있는지를 통해서 최소한의 시간을 이분탐색으로 찾아나가는 것이다.

 

예를들면,

 

left는 최소시간, right는 최대시간을 기준으로 하면

테스트케이스 기준으로 left=1, right=60이 된다.

left 1 mid 30 right 60 일 때,

mid 를 [7, 10] 으로 각각 나누어 ppl에 추가하면 4+3 = 7 이며,

n이 6이기 때문에 answer=30, 그리고 right를 29로 줄여주면서

계산을 쭉하면 결국 28에 수렴하게 된다.

 

 

 

 

 

도움이 되셨다면 공감 부탁드립니다.