[sort] 백준 3079번 - 입국심사

 

N개의 입국심사대

M명의 입국자

 

시간대로 본다면 결국 분 대별로 각 심사대 라인에서 수용할 수 있는 인원이 정해진다

결국 시간이 늘어날 수록 심사완료할 수 있는 수가 늘어나는 정렬의 구조! -> 이분 탐색

최대의 시간 = 입국자가 10^9일 때 1개의 줄이 있는 경우 = 10^18

int 형은 10^9 -> long long 자료형 사용한다

 

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#define endl '\n'
#define DIV 1000000009

long long N, M;
int gate[1000000];


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    cin>>N>>M;
    int input;
    for(int i=0; i<N; i++){
        cin>>input;
        gate[i] = input;
    }
    long long high = 1e18;
    long long low = 1;
    long long mid = 0;
    long long sum = 0;
    long long result = 0;
    while(low<=high){
        mid = (high+low)/2;
        sum = 0;
        for(int i=0; i<N; i++){
            sum += mid/gate[i];
            if(sum>=M) 
                break; //sum에 대한 overflow가 일어날 수 있다
        }
        if(sum<M){
            low = mid+1;
        }
        else if(sum>=M){
            result = mid;
            high = mid-1;
        }
    }
    cout<<result<<endl;

}