[백준 3079] 입국심사 (C++)

문제 링크: https://www.acmicpc.net/problem/3079

3079번: 입국심사

1. 주의할 점

- 이분탐색으로 접근하며 High의 값은 가장 오래걸리는 심사대 X 사람수로 설정한다.

- 결과값에 따라 어떤 경우 Low를 높이고, 어떤 경우에 High를 낮출지 잘 정한다(등호 하나만 잘못써도 틀린다).

 

2. 구현

- Low: 0, High: 가장 오래걸리는 심사대 X 사람수, Mid: Low + (High - Low)/2 로 설정한다.

- Mid를 (Low+High)/2 로 설정하지 않는 이유는 Low+ High가 설정한 변수의 최대 범위를 넘어서는 경우 -로 들어오기 때문에 그런일이 발생하지 않도록 미리 예방한다.

- Mid 시간에 몇명의 사람을 각 심사대가 검사할 수 있는지 확인하여 Sum에 더한다.

- Sum >= People인 경우, Mid 시간에 People의 사람만큼 충분히 검사할 수 있다.

   -> 더 짧은 시간에도 가능한가? => High = Mid - 1

- Sum < People인 경우, Mid 시간에 People의 사람만큼 충분히 검사할 수 없다.

  -> 시간을 더 주면 가능한가?  => Low = Mid + 1

 

#include <iostream>
#include <algorithm>
using namespace std;
long long arr[100000];
int num, people;
long long low, high, mid, result;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> num >> people;
	low = 0;
	high = 0;
	for (int i = 0; i < num; i++) {
		cin >> arr[i];
		high = max(high, arr[i]);
	}
	high *= people;
	while (low <= high) {
		long long sum = 0;
		mid = low + (high - low) / 2;
		for (int i = 0; i < num; i++)
			sum += mid / arr[i];
		if (sum < people)
			low = mid + 1;
		else {
			result = mid;
			high = mid - 1;
		}
	}	
	cout << result;
	system("PAUSE");
	return 0;
}