백준 3079(입국심사)

N개의 줄에 M명이 통과할 수 있는 최소 시간을 구해라 

 

어떤 값을 구하려고 할 때 그 값이 맞는지 안 맞는지 확인 할 수 있는 문제면서, 그 조건이 정렬된 경우에는 이분탐색으로 풀 수 있는 것같다. 

 

min heap에 조건을 추가해서 구할 수도 있다고 생각을 했지만 구체적인 구현이 불가한것 같아서 스킵하였다.

 

일반적인 이분탐색문제와 같이 경계값을 설정한 뒤에 mid값이 원하는 조건을 만족하는지 찾으면 된다. 

 

적절하게 최댓값, 최솟값을 설정한다. 이 때 최댓값의 크기는 시간에 별 영향을 안주는 것 같지만 (logn의 속도이므로)

 

잘못하면 right + left의 최대크기 때문에 오버플로우가 발생할 수 있기 때문에 조심한다. 

 

이것도 while(right>=left) right = mid - 1; left = mid + 1; 로 어떤 값이 원하는 조건에 맞는지 확인 후 원하는 값까지 빠르게 다가가서 그 값이 맞는 것 중에서 최대 or 최소를 찾으면 된다. 

(찾는 어떤 것이 선형적? 이면 찾을 수 있는 것 같다.)

 

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX 100000

long long N, M, left_n, right_n, mid, sum, min_t;
int line[MAX];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> line[i];
	}
	sort(line, line + N);
	right_n = line[0] * M;
	left_n = 1;
	min_t = right_n;
	while (right_n >= left_n) {
		mid = (right_n + left_n) / 2;
		sum = 0;
		for (int i = 0; i < N; i++) {
			sum += mid / line[i];
		}
		if (sum >= M) {
			if (mid < min_t)min_t = mid;
			right_n = mid - 1;
		}
		else {
			left_n = mid + 1;
		}
	}
	cout << min_t << "\n";

}