[C++] 프로그래머스 - 입국심사 / 바이너리 트리

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

 

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

입출력 예

n times return

6

[7, 10]

28

 

사실 이분탐색 개념을 처음 듣고 공부하는거라 이번 문제는 구글링 참고 90으로 푼 것 같다.

풀이보단 공부...

 

left<right는 디폴트지만 left=min, right=max라고 두고 이때 max는 가장 오래 걸리는 시간이기 때문에

times중 가장 큰 원소 * n인 것이다.

 

 

바이너리 검색시 방법은, 미리 정렬된 데이터를 대상으로 반으로 나눠서 비교하기 때문에

가운데에 있는 데이터의 키 값이랑 비교해야 한다.

찾으려는 데이터보다 작으면 왼쪽, 크면 오른쪽으로 이동하는 방식이다. 

 

min이 max보다 커질 때까지 while문을 반복하여 찾는다.

 

 

#include <string>
#include <vector>
#include <algorithm>

typedef longlong ll;

using namespace std;

ll solution(int n, vector<int> times) {
    sort(times.begin(), times.end());
    
    
    ll right = (ll)times.back()*n; //right==max 최댓값임
    ll left = 0;
    ll mid;
    ll count=0;
    ll answer = right;
    
    while(left<=right){ 
        ll count =0;
        mid=(left+right)/2;
        
         for (int i = 0; i < times.size(); i++) {
            count += mid / times[i];
        }
        if (count < n) {
            left = mid + 1; //불가능하면 시간을 더 많이
        }
        else{
            if (mid <= answer) 
                answer = mid;
            right = mid - 1; //가능하면 시간 줄이기
        }
    }
    
    
    return answer;
}