프로그래머스. 입국심사(c++) / 이분탐색

도저히.. 풀이가 생각이 나지 않아 다른 블로그의 아이디어만 참고해서 가닥을 잡을 수 있었다.

 

[메인 로직]

모든 경우의 수 중에서 가장 최악의 시간이 나올 경우를 찾는다.

ex) [7, 10], n = 6이면

최악의 시간은 10분이 걸리는 심사관에게 6명 모두가 입국심사를 받는 경우가 될 것이다.

그러면 최악의 시간은 총 60분이다.

 

Start = 1, End = 60으로 하고 이분탐색을 시작하면 된다.

mid = (Start+End)/2로 잡고 mid의 시간일 때 총 검사할 수 있는 인원의 수를 구한다.

30/7+30/10 = 7은 n=6의 값보다 크기 때문에 End = mid-1로 이분탐색을 쭉 진행하면 된다.

단! 조심해야하는 부분은 n값과 같은 값이 나왔다고 해서 바로 break로 빠져나오면 오답이다.....

더 작은 시간에서도 n과 같은 값이 나올 수도 있기 때문에 같을 경우에도 End = mid-1로 해서 계속적으로 탐색하는 것이 중요한 포인트이다!!

 

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#include <climits>
 
using namespace std;
 
long long solution(int n, vector<int> times) {
 
    sort(times.begin(), times.end());
 
    long long Start = 1;
    long long End = (long long)times[times.size()-1]*n;
    long long answer = End;
    
    while(Start<=End){
        long long mid = (Start+End)/2;
        long long sum = 0;
        for(int i=0; i<times.size(); i++){
            sum += (mid/times[i]);
        }
                
        if(sum>=n){
            answer = min(answer, mid);
            End = mid-1;
        }else if(sum<n){
            Start = mid+1;
        }
        
    }
    
    return answer;
}