[프로그래머스] 입국심사

링크

https://programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

풀이

 

 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 구하는 문제이다.

 

1부터 입국 심사하는 시간에 맞춰 입국 심사를 하는 사람을 카운트하게 되면 시간 초과가 날게 분명하다.

 

그래서 -> n시간/(입국 심사를 하는데 걸리는 시간) 을 하면 n시간에 도달하였을 때 입국 심사를 받을 수 있는 사람의 수를 구할 수 있다. 이것을 이용하여 문제를 풀었는데

 

이때 n시간을 구하기 위해서 시간을 이분탐색으로 찾았다.

 

n시간/(입국 심사를 하는데 걸리는 시간) 을 하였을 때 구하고자 하는 사람의 수보다 많다면 n시간을 줄이고

n시간/(입국 심사를 하는데 걸리는 시간) 을 하였을 때 구하고자 하는 사람의 수보다 적다면 n시간을 늘리도록 하였다.

 

이분 탐색을 이용하여 알맞은 시간을 구할 수 있다.

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>

#define SIZE 1010
const int INF = 2000000000;

using namespace std;

typedef long long int ll;
typedef unsigned long long ull;
long long solution(int n, vector<int> times) {

	//시간을 기준
	ll left = 1, right = 1844674407370955161, mid;

	while (left <= right) {
		mid = (left + right) / 2;

		ll human = 0;
		for (auto time : times) {
			human += mid / (ll)time;

			if (human >= n)
				break;
		}

		if (human >= n) {
			right = mid - 1;
		}
		else
			left = mid + 1;
	}
	
	return right +1;
}