3079번 입국심사

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

이분 탐색 파라메트릭 서치 결정값 boj 백준 필수 복습 코테 코딩 최적화 공부

"이 시간(초) 동안 입국 심사를 모두 완료할 수 있는가?"

예제 1 설명

에를 들어 30초 일 때,

30 / 7 = 4

30 / 10 = 3

-> 7명이다. 

m(6)보다 크므로 Right = mid(30) - 1로 하면서 계속 줄인다.

28초라고 할 때,

28 / 7 = 4

28 / 10 = 2

6명이다. 

계속 진행을 해보면 28이 최솟값임을 알 수 있다.

핵심은

1.

해당 시간(Time) 동안 입국 심사대에서 입국 심사를 모두 완료할 수 있는 인원 수 

= Time / 해당 입국 심사대에서 심사하는데 걸리는 시간

2.

최댓값은 입력으로 주어진 입국 심사대에서 걸리는 시간 중 최댓값과 m을 곱하여 Right로 설정하는 것이다.

이다.

#include<bits/stdc++.h>
 
using namespace std;
 
#define LL long long
 
LL n, m, Max;
vector<LL> v;
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    scanf("%lld %lld", &n, &m);
 
    v.assign(n, 0);
    for (int i = 0; i < n; i++) {
        scanf("%lld", &v[i]);
        Max = max(Max, v[i]);
    }
 
    sort(v.begin(), v.end());
 
    LL Left = 0, Right = Max * m + 1;
 
    LL answer = LLONG_MAX;
    while (Left <= Right)
    {
        LL mid = (Left + Right) / 2LL;
 
        LL total = 0;
        for (int i = 0; i < n; i++) {
            total += (mid / v[i]);
        }
 
        if (total < m) {
            // total이 m보다 작다면 정답은 [mid, Right]에 있다.
            // 즉, mid 늘리면 total이 커질 것이고, m에 더욱 가까워 지기 위해 mid + 1을 Left에 대입한다.
            Left = mid + 1;
        }
        else {
            // m 이상이라면 최대한 줄인다.
            answer = min(answer, mid);
            Right = mid - 1;
        }
    }
 
    printf("%lld\n", answer); // or Left
 
    return 0;
}