백준 3079번 입국심사 - C++ 풀이

---

 

1. t초동안 심사할 수 있는 사람 수의 최댓값은 ∑(t / Tk)이다.
2. 파라매트릭 서치를 사용하여 M명을 모두 처리할 수 있는 최소 시간을 구한다.

 

1. t초동안 심사할 수 있는 사람 수의 최댓값은 ∑(t / Tk)이다.

 t초동안 심사할 수 있는 사람 수를 최대로 하려면, 각 심사대가 쉬지 않고 일을 해야 한다. 따라서 각 심사대가 t / Tk명을 처리할 수 있고 이를 모두 더하면 t초 동안 심사할 수 있는 사람의 수의 최댓값을 구할 수 있다. 시간복잡도는 O(N).

 

2. 파라매트릭 서치를 사용하여 M명을 모두 처리할 수 있는 최소 시간을 구한다.

 M명을 모두 처리할 수 있는 최소 시간을 min_t라고 하면, t >= min_t인 경우 항상 모든 사람 심사가 가능하고 t < min_t인 경우 항상 모든 사람 심사가 불가능하다. 따라서 파라매트릭 서치를 사용하여 최적값을 찾을 수 있다. t의 최댓값이 min(Tk)*M이므로 총 시간복잡도는O(NlogTM).

 

---

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;
const int MAX_N = 100'001;

int N, M;
ll T[MAX_N];

// dicision(t): t초 안에 심사를 마칠 수 있는가?
bool decision(ll t) {
    ll cnt = 0;
    
    // 각 심사대별로 t초동안 처리할 수 있는 사람 수 구하기
    for (int i=0; i<N; i++) {
        cnt += t / T[i];
        if (cnt >= M) break;
    }
    
    return cnt >= M;
}

// optimize(): 입국 심사를 마치는데 걸리는 시간을 최소화
ll optimize() {
    ll lo = 0, hi = T[0] * M;
    
    // 파라매트릭 서치
    while (lo+1 < hi) {
        ll mid = (lo+hi)/2;
        if (decision(mid)) hi = mid;
        else lo = mid;
    }
    
    return hi;
}

int main() {
    cin >> N >> M;
    for (int i=0; i<N; i++) cin >> T[i];
    sort(T, T+N);
    
    cout << optimize();
    
    return 0;
}