소스 코드

// swea 3074 입국심사
#include <iostream>
#include <vector>
#define endl "\n"

using namespace std;

typedef long long ll;

int m; // 사람 수
int n; // 심사대 수
vector<ll> t; // 심사 시간
ll maxT; // 최대 심사 시간

void solve();
void input();
ll binarySearch(ll left, ll right);
ll getNum(ll m);

int main()
{
	//freopen("sample_input_swea_3074.txt", "r", stdin);
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int TC;
	cin >> TC;
	for (int tc = 1; tc <= TC; ++tc)
	{
		cout << "#" << tc << " ";
		solve();
	}

	return 0;
}

void solve()
{
	input();

	ll left = 0;
	ll right = maxT * m;

	cout << binarySearch(left, right) << endl;
}

void input()
{
	cin >> n >> m;

	maxT = -1;
	t = vector<ll>(n);
	for (int i = 0; i < n; ++i)
	{
		cin >> t[i];

		if (t[i] > maxT)
		{
			maxT = t[i];
		}
	}
}

ll binarySearch(ll l, ll r)
{
	while (l < r)
	{
		ll mid = l + (r - l) / 2;
		
		if (m <= getNum(mid))
		{
			r = mid;
		}
		else
		{
			l = mid + 1;
		}
	}

	return l;
}

ll getNum(ll m)
{
	ll sum = 0;

	for (int i = 0; i < n; ++i)
	{
		sum += m / t[i];
	}

	return sum;
}

해설

총 m명에 대해 최소 시간 계산 시 O(m), m <= 10^9 이므로 시간초과. 따라서 시간복잡도를 줄일 수 있는 알고리즘을 생각해 내야 한다.

가능한 최소 시간은 0초와 (최대 심사 시간 * m) 사이에 존재할 것이므로 이분탐색 알고리즘 진행 시 O(log(10^9 * 10^9)) ~= O(60) 이므로 시간 초과 문제 해결.

left = 0(초), right = 최대심사시간 * m(초)로 초기 값 설정 후 이분탐색 진행