[백준] 3079번 입국 심사

문제 링크

프로그래머스

 

풀이

심사대의 범위가 1 ~ 100,000이고 친구들의 숫자가 최대 10억명이므로 이분 탐색을 사용하지 않으면 시간이 너무 오래 걸리게 될 겁니다. 이 문제에서는 어디에 이분 탐색을 사용해야 할까요. 우리가 구하고자 하는 답은 주어진 인원이 입국 심사 하는 데 걸리는 최소 값입니다. 입국 시간과 인원과의 상관 관계를 먼저 생각해볼게요. 예제에서 두 개의 심사대가 주어지고 각각 심사 시간이 7분, 10분입니다.

 

만약 입국자에게 5분이 주어진다면 어느 누구도 심사대를 통과할 수 없을 겁니다. 7분이면 1명만 통과할 수 있고요 10분은 돼야 2명이 받을 수 있습니다. 직관적으로 계산할 수 있지만 수식으로 해보면, 주어진 시간이 X일 때 각 심사대의 심사 시간을 나눈 값을 더한 총합입니다. 즉 주어진 시간이 10분일 때 10/7 + 10/10 = 2이기 때문이 두 명인 것이죠. 이분 탐색의 대상은 시간입니다. 최소값을 1로 두고 최대값은 입국 심사가 가장 긴 시간에 모든 사람이 몰렸을 때 걸리는 시간입니다. 이 사이에서 이분 탐색을 통해 주어진 친구들의 수와 일치하는 값을 찾으면 됩니다.

 

이분 탐색의 탈출조건을 생각해봐야하는데요. 우리는 최소값을 구할 겁니다. 어떤 특정 값을 구하는 것이면 수 찾기 문제에서처럼 else 조건으로 존재 여부를 파악하면 되지만, 이 문제는 최소 값을 구하는 것이기 때문에 떨어지는 값이 없을 수 있습니다. 최소값을 구하는 것이므로 마지막 low값이 정답이 됩니다. 혹은 else 조건에 들어오는 마지막 mid 값도 정답입니다. 답이 long long 타입인 이유는 심사 시간의 범위가 10^9이고, 심사대의 개수가 10^5이기 때문입니다.

 

코드

#include <cstdio>
int main()
{
	int N, M;
	int e[100000] = {};
	scanf("%d%d", &N, &M);
	long long high = 0;
	for (int i = 0; i < N; ++i)
	{
		scanf("%d", &e[i]);
		high = high < e[i] ? e[i] : high;
	}

	high = high * M;
	long long low = 1;
	// long long answer = 0;
	while (low <= high)
	{
		long long m = 0;
		long long mid = (low + high) / 2;		
		for (int i = 0; i < N; ++i)
			m += mid / e[i];
		if (m < M)
			low = mid + 1;
		else
		{
			//answer = mid;
			high = mid - 1;
		}
	}
	printf("%lld\n", low);
	//printf("%lld\n", answer);
}