boj, 백준) 3079. 입국심사 ( C / C++)

1. 문제 링크

https://www.acmicpc.net/problem/3079

3079번: 입국심사

2. 문제 개요

친구들은 총 M명이고, 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다.

각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. K번 심사대에 앉아있는 심사관이 한 명을 심사하는데 드는 시간은 Tk이다.

 

심사관은 한 번에 1명만 심사할 수 있고, 줄의 가장 앞에 서 있는 사람은 비어있는 심사대가 보이면 거기로 가서 심사를 받을 수 있다. 하지만 항상 이동은 하지 않아도 된다. 더 빠른 심사대의 심사가 끝나길 기다린 다음에 그곳으로 가서 심사를 받아도 된다.( 비어있는 심사관은 100초 걸림. 1초 뒤에 10초 만에 하는 심사관이 빈상태가 됨. 1초 기다렸다가 10초 만에 하는 심사관에게 받아도 됨.)

 

이럴 때.. 모든 친구들이 심사를 받는데 걸리는 시간의 최솟값을 구하는 프로그램을 만들자.

 

3. 문제 힌트

심사를 마치는데 걸리는 시간을 이분 탐색한다.

정답을 X이라고 가정.

시간 X동안 1명당 시간 Y이 걸리는 심사관은 총 X/Y (몫만) 명을 최대로 처리할 수 있다.

즉, 10분 동안 1명당 3분이 걸리는 심사관은 최대 3명을 처리할 수 있다는 것.

 

결괏값에 따라 이분 탐색 구간을 변경해보자.

 

4. 문제 풀이

(3) 번에 적은 것처럼

정답을 X라고 가정하고 들어간다.

위의 방식대로 계산하고 처리할 수 있는 사람이 친구보다 많으면 가정한 X시간은 모두 심사를 받을 수 있으니 저장하고

최솟값을 찾으러 right = mid-1로 시간을 줄인다.

 

반대의 경우, 처리할 수 있는 사람이 친구보다 적으면 시간이 부족하다는 의미고 따라서 X를 증가시키기 위해 left = mid +1로 시간을 높인다.

 

5. 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
vector<int> v;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;
	v.resize(n);
	long long int maxval = 0;
	for (int i = 0; i < n; ++i) {
		cin >> v[i];
		maxval = max((long long int) v[i], maxval);
	}


	long long int left = 1, right = maxval*m;
	long long int ans = 0;
	while (left <= right)
	{
		long long int mid = left +(right - left) / 2;

		long long int sum = 0;
		for (int i = 0; i < n; ++i)
			sum += mid / v[i];

		if (sum < m)
		{
			left = mid + 1;
		}
		else
		{
			ans = mid;
			right = mid - 1;
		}
	}
	cout << ans;
	return 0;
}

6. 결과 사진

 

지적, 댓글 언제나 환영입니다~