(C++) - 백준(BOJ) 3079번 : 입국심사 답

www.acmicpc.net/problem/3079

3079번: 입국심사

이분탐색 문제였습니다. 

 

풀이방법

1부터 가장 오래걸리는 입국심사대의 시간*m명의 범위에서 소요시간을 탐색하면 답을 구할 수 있습니다.

심사대마다 처리할 수 있는 사람 명 수는 각 걸리는 소요시간 / 심사대의 심사 소요시간이 됩니다.

따라서 모든 심사대마다 해당공식을 적용하여 나온 결과값을 더한 결과가 m명 이상일 때 소요시간에 대한 답을 구한 것이고 이들 소요시간 답들 중 최소값이 우리가 구하려는 답입니다.

 

*탐색 범위를 주의해야합니다. int는 대략 21억까지의 정수를 저장할 수 있는 자료형입니다. 따라서 int 범위를 넘을 수 있으니 처리할 수 있는 자료형으로 변수를 선언해 주시는 것이 답을 맞추는 지름길입니다 

 

Code

#include <iostream>
#include <algorithm>
#define ll long long
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
ll n,m;
ll times[100001];
ll MAX;
ll binarySearch(){
    ll ansTime = MAX * m;

    ll l = 1;
    ll r = MAX * m;
    while(l<=r){
        ll mid = (l+r)/2;
        ll sum  =0;
        for(ll i = 0; i < n; i++){
            sum += mid / times[i];
        }
        if(sum >= m){
            ansTime = min(ansTime,mid);
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    return ansTime;
}
int main(){
    fastio;
    cin >> n >> m;
    for(ll i = 0; i < n; i++){
        cin >> times[i];
        MAX = max(MAX,times[i]);
    }
    sort(times,times+n);
    cout << binarySearch() << '\n';
}