프로그래머스 - 입국심사 링크
(2023.08.28 기준 Level 3)
(치팅하지 마세요)

문제

n명이 입국심사를 위해 기다리고 있다.
각 심사대마다 한 명을 심사하는데 걸리는 시간이 주어지며, 한 심사대에서는 동시에 한 명만 심사를 받을 수 있다.
모든 사람이 심사를 받는데 걸리는 최소 시간 반환

알고리즘

이분 탐색

풀이

n이 최대 1,000,000,000명이라 단순 시뮬레이션으론 구할 수 없다.

심사대에선 한명이 끝나면 바로 다음 사람을 받을 수 있다.
결국은 모든 심사대는 걸리는 시간에 반비례하여 사람을 받아야 최대로 걸리는 시간을 줄일 수 있다.
이 말을 다른 관점에서 살펴보면? 총 걸리는 시간을 잡아두면 모든 심사대에선 걸리는 시간에 반비례하여 받을 수 있는 사람 수가 정해질 것이다.

그러니깐 총 심사하는 시간을 이분 탐색으로 조절하면서, 모든 심사대에서 받을 수 있는 총 사람 수를 구하면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll solution(int n, vector<int> times){

    // 입국심사를 기다리는 사람 1,000,000,000명이고
    // 심사관은 1명이며 심사하는데 걸리는 시간은 1,000,000,000분일 때
    // 시간은 최대 1,000,000,000,000,000,000분 걸린다.
    ll st = 1, en = 1000000000000000000;

    // 이분탐색으로 각 심사관마다 총 심사하는 시간 제한을 걸었을 때
    // 가능한 최대로 심사할 수 있는 사람들을 구하여
    // 입국심사를 기다리는 사람 수를 넘는지 확인하면 된다.
    while (st < en){
        ll mid = (st + en) >> 1;
        ll possible = 0;
        for (auto time: times) possible += mid / time;
        if (possible < n) st = mid + 1;
        else en = mid;
    }

    return st;
}

• Python

def solution(n, times):

    # 입국심사를 기다리는 사람 1,000,000,000명이고
    # 심사관은 1명이며 심사하는데 걸리는 시간은 1,000,000,000분일 때
    # 시간은 최대 1,000,000,000,000,000,000분 걸린다.
    st = 1; en = 1000000000000000000

    # 이분탐색으로 각 심사관마다 총 심사하는 시간 제한을 걸었을 때
    # 가능한 최대로 심사할 수 있는 사람들을 구하여
    # 입국심사를 기다리는 사람 수를 넘는지 확인하면 된다.
    while st < en:
        mid = (st + en) >> 1
        possible = sum(mid // time for time in times)
        if possible < n:
            st = mid + 1
        else:
            en = mid

    return st