[ 백준 ] 3079번 - 입국심사 (C++)

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

3079번: 입국심사

 

 

[ 문제풀이 ]

 

1. 심사대의 걸리는 시간을 arr 배열에 저장하고, 그 값 중 가장 작은 값을 저장합니다.

 

2. s = 0, e = Min * M + 1로 설정한 후 이분 탐색을 통해 해당 시간 안에 모두 통과가 가능하다면 e = m을 적용하고, ans = e를 해주고, 통과가 불가능하다면 s = m + 1을 적용해 줍니다.

 

3. 이분 탐색이 끝난 후 ans를 출력해 줍니다.

 

[ 소스코드 ]

#include<iostream>
#define ll long long
 
using namespace std;
int arr[100000];
int N, M;
 
bool check(ll mid)
{
    ll num = 0;
 
    for (int i = 0; i < N; i++) {
        num += mid / arr[i];
 
        if (num >= M) {
            return true;
        }
    }
 
    return false;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    int Min = 1111111111;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
        Min = min(Min, arr[i]);
    }
 
    ll s = 0;
    ll e = 1LL * Min * M + 1;
    ll ans = 0;
 
    while (s < e) {
        ll m = (s + e) / 2;
 
        if (check(m)) {
            e = m;
            ans = e;
        }
        else {
            s = m + 1;
        }
    }
 
    cout << ans;
}