입국심사 3079

23.06.15 수정

문제

접근 방법

프로그래머스의 입국심사랑 이름부터 같다. 동일하게 풀어주면 된다.

코드 (23.06.15 수정)

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int N, M;
    ll high = 0, low = 0, mid, ret;
    vector<int> times;
    cin >> N >> M;
    for (int i = 0; i < N; ++i)
    {
        int time;
        cin >> time;
        times.push_back(time);
        if (high < time)
            high = time;
    }
    high = M * high;
    while (low <= high)
    {
        ll sum = 0;
        mid = (low + high) >> 1;
        for (int time : times)
        {
            sum += mid / time;
            if (sum >= M)
                break;
        }
        if (sum >= M)
        {
            high = mid - 1;
            ret = mid;
        }
        else
            low = mid + 1;
    }
    cout << ret;
    return 0;
}

풀이

int 범위를 넘는 것을 생각하며 코드를 작성하면 된다.
나눠서 합한 값을 기준으로 low, high를 조정하면 된다.

하지만 한 가지 문제가 존재하는데 각 심사대에서 수용할 수 있는 인원을 합해주는 과정에서 오버플로가 발생한다. 해결하기 위해선 만약 M보다 크다면 이미 걸리는 시간의 최솟값 이상이라는 것이므로 합하는 것을 멈추고 진행하면 된다.