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

문제

백준 3079

3079번: 입국심사

풀이

경곗값 설정을 잘 못해서 고생 좀 했습니다.

최소 시간의 최댓값은 1 1000000000 1000000000 경우의 1000000000000000000입니다.

따라서 이분 탐색 시에 최솟값을 1, 최댓값을 1000000000000000000으로 설정해야 합니다.

그 후에는, 배열을 돌면서 sum에 해당 심사대 에서 입국할 수 있는 사람의 수(mid/arr[i])를 더해줍니다.

sum 값이 목표값 보다 크거나 같으면 end = mid -1로 더 최솟값을 찾고

sum 값이 목표값 보다 작으면 start = mid + 1로 더 큰 시간에서 조건을 만족하는 값을 찾습니다.

소스 코드

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 
int arr[100000];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    // end 값에 유의
    long long start = 1, end = 1000000000000000000;
    long long mintime = end;
    while (end >= start)
    {
        long long mid = (start + end) / 2;
        long long sum = 0;
        for (int i = 0; i < n; i++)
        {
            // mid 시간에 통과할 수 있는 사람 계산
            sum += mid / arr[i];
            if (sum >= m)
                break;
        }
        // 통과할 수 있는 사람 수가 조건보다 많으면
        if (sum >= m)
        {
            mintime = min(mintime, mid);
            end = mid - 1;
        }
        // 통과할 수 있는 사람 수가 조건보다 적으면
        else
        {
            start = mid + 1;
        }
    }
    cout << mintime;
    return 0;
}