백준 3079 입국심사 c++ [컴공과고씨]

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

3079번: 입국심사

이 문제는 처음에 감을 잘 못잡았다. 처음에는 최소 시간을 구하려는 방법을 생각하니 당연히 답이 나올 수 없었다.

그래서 고민 좀 많이 하고 생각을 바꿔서 시간을 기준으로 해서 각 시간마다 얼만큼의 사람을 통과시킬 수 있는지로 구현을 하여서 심사할 수 있는 인원의 조건을 만족하는 시간 중에서 최소값을 찾아주는 식으로 구현하였다.

중요한 것은 범위가 엄청 크기때문에 시간초과에 걸릴 수 있어 각 시간마다 검사 수를 탐색할때 이분탐색을 활용하여 구현 했다. 

x시간 동안 검사할 수 있는 인원 수는 (x 시간)/(심사대가 걸리는 시간)을 각 심사대에 적용하여 전부 더해주면 된다.

이 식은 직접 해보면 쉽게 이해할 수 있다.

 

전체 코드

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
    unsigned long long n, m;
    unsigned long long t[100001];
    cin >> n >> m;
    for (int i = 0; i < n;i++){
        cin >> t[i];
    }
    sort(t, t + n);
    unsigned long long high = m * t[0]; 
    // 심사 시간이 제일 적은 데스크에 모든 사람이 검사 받는 경우를 최대 값으로 잡아줌
    unsigned long long low = 1;
    unsigned long long mid;
    unsigned long long ans = 0;
    unsigned long long people;
    while(high >= low){ // 이분탐색
        people = 0;
        mid = (high + low) / 2;
        for (int i = 0; i < n;i++){
            people += mid / t[i]; // mid시간에 검사할 수 있는 인원 수
        }
        if(people >= m){ // 검사 인원이 주어진 인원이랑 같거나 커야 조건 만족
            if(ans > mid || ans ==0){ // 최소시간일때 답 저장
                ans = mid;
            }
            high = mid - 1;
        }
        else{
            low = mid + 1;
        }
    }
    cout << ans;
    return 0;
}

사용 알고리즘 : 이분탐색

 

yea!