[백준 3079번 / C++] 입국심사

이분탐색 문제이다. 

 

해당 문제는 프로그래머스 입국심사 문제와 거의 똑같다고 보면된다. 

(사실, 그때 너무 열 받았던적이..) 

 

#접근방법 

이분탐색에 대한 알고리즘을 모른다면 이분탐색 개념을 익히고 오는 것을 추천한다. 

 

먼저 양쪽 끝 값을 설정해야 하는데 low와 high라는 변수를 둔다. 

해당 변수들은 각각 제일 적게 걸리는 시간과 제일 오래 걸리는 시간을 초기화한다. 

 

즉, low에는 0을 두고 high 에는 max.time[i] * m 을 둔다. 

 

high 초기화 값이 왜 저렇게 되는지 모를 수도 있는데

이게 무슨 말이냐면, 심사대 중 제일 시간이 오래 걸리는 심사대에 m명의 사람이 다 줄을 설수 있다. 

그래서 최악의 상황에서 나올 수 있는 값을 high 값에다가 세팅 해주는 것이다. 

 

이후 절반을 쪼개가면서 탐색을 하게되는데, 

mid 값은 시간이다. 예를 들면, 

mid 값이 10000000초에서 심사대 시간 time[i] 배열로 각각 나눈 값들의 합은

수용할 수 있는 사람의 수이다. 100초 동안 10초의 심사가 걸리는 심사대로 나누면 100초동안 10명을 수용할 수 있는 것처럼. 

 

이런식으로 m명의 사람보다 더 큰 값이 나온다면 high값을 mid-1 로 세팅.

m명의 사람보다 작다면 low 값을 mid+1 로 세팅한다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std; 
typedef long long ll;
vector <ll> time;
ll n, m;
bool check(ll mid) {	
	ll number = 0; 
	for (int i = 0; i < n; i++) {
		number += mid / time[i]; 
	}
	if (number >= m)return true;  
	else return false; 
}


int main() {
	ios::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0); 
	cin >> n >> m; //n은 심사대, m 사람 수 
	time.resize(n, 0); 
	ll low, high, result; 
	low = high = result = 0;  
	for (int i = 0; i < n; i++) { 
		cin >> time[i]; 
		high = max(high, time[i]); 
	}
	high *= m; 
	result = high; 	
	while (low <= high) {
		ll mid = (low + high) / 2; 
		if (check(mid)) {
			high = mid - 1; 
			result = mid; 
		}
		else low = mid + 1; 
	}
	cout << result; 
	return 0; 
}

 

3079번: 입국심사