[Algorithm]Baekjoon 3079번 :: 입국심사

https://www.acmicpc.net/problem/3079

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
#include <cmath>
#include <mutex>
 
using namespace std;
 
 
int n, m; // n 10만, m 10억
int processingTimes[100000] = { 0 };
 
 
bool check(unsigned long long time)
{
    // time이내에 m명이 전부 통과할 수 있는지를 체크해야됨.
    // m값 최대 10억
 
    unsigned long long sum = 0;
 
    for (int i = 0; i < n; ++i) // 심사대 시간들
    {
        sum += time / processingTimes[i];
 
        if (sum >= m)
        {
            return true;
        }
    }
 
    return false;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> m;
 
    for (int i = 0; i < n; ++i)
    {
        cin >> processingTimes[i];
    }
 
    sort(processingTimes, processingTimes + n);
 
    unsigned long long left = 0;
    unsigned long long right = pow(10, 18);
    unsigned long long answer = 0;
 
    while (left <= right)
    {
        unsigned long long mid = (left + right) / 2;
 
        if (check(mid))
        {
            right = mid - 1;
            answer = mid;
        }
        else
        {
            left = mid + 1;
        }
    }
 
    cout << answer;
}

 

구해야하는 최소시간을 mid값을 두고 이분탐색하면 되는데, 이 때 정해진 시간을 두고 이 시간 내에 모든 인원이 통과할 수 있는지를 알아내는게 포인트다.

이 유형이 꽤 알고리즘문제에서 자주 나오는 유형인 것 같긴하다.

생각보다 쉬운데, 그냥 각 심사대시간으로 나눠준 몫을 합쳤을 때 인원수 이상이면 전부 통과할 수 있다고 판단한다.

 

전부 검사할 필욘 없으니, 처음에 심사대시간을 오름차순 정렬시켜주고 반복문 돌 때 인원수 넘기면 바로 true를 리턴하게 해주면 된다.