백준 3079번. 입국심사(c++) / 이분탐색

프로그래머스에도 동일한 문제가 있다. 하지만, 차이점이라고 한다면 백준 문제는 입력값의 범위가 훨씬 크기 때문에 잘 고려해서 코드를 구현해야한다.

 

[메인 로직]

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

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

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

Start = 0, End = 60(최악시간)으로 하고 이분탐색을 시작하면 된다.

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

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

 

[중요한 포인트]

계산한 값과 m을 비교할 때, 같을 경우에도 바로 break해서 빠져나오는 것이 아니라

어차피 최솟값을 구하는 것이기 때문에 End = mid-1로 해준다.

 

// 입국심사
#include <vector>
#include <climits>
#include <iostream>
using namespace std;
 
int n, m;
long long a;
long long maxWait = 0;
vector<long long> v;
long long ans = 1000000000000000001;
 
int main()
{
    cin>>n>>m;
    for(int i=0; i<n; i++){
        cin>>a;
        maxWait = max(maxWait, a);
        v.push_back(a);
    }
 
    long long Start = 0;
    long long End = maxWait*m;
 
 
    while(Start<=End){
        long long mid = (Start+End)/2;
        long long tmp = 0;
        for(int i=0; i<v.size(); i++){
            tmp += (mid/v[i]);
        }
 
        if(tmp>=m){
            ans = min(ans, mid);
            End = mid-1;
        }else{
            Start = mid+1;
        }
    }
 
    cout<<ans<<"\n";
    return 0;
}