어떻게 심사를 받으면 모든 사람이 심사를 받는데 걸리는 시간이 최소가 될 지 궁금함 (최소 시간을 구해야 함)
1-2. 입력값과 출력값
//예제 입력
2 6 // 앞의 2는 심사대의 갯수, 뒤의 6은 입국심사를 받아야 할 사람의 수.
7
10
// 7과 10은 각각 심사대에서 한 명을 처리하는데 걸리는 시간.
//예제 출력
28
첫째줄에 입국심사대 갯수 N과 입국 심사를 받아야 할 사람의 수 M이 주어짐
다음 N개의 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어짐
출력으로는 상근이와 친구들이 심사를 마치는데 걸리는 시간의 최솟값을 출력하면 됨
1-3. 문제조건
1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000
1 ≤ Tk≤ 10^9
사용하는 로직에 따라서 자료형을 어떤걸 사용할 지 주의해야 함
2.문제풀이
2-1. 준비물
(1) 입력 받을 배열과
unsigned long * inspect = new unsigned long[N];
// 이분탐색 중에 mid 값을 구할 때, left와 right를 더하는 연산이 있고
// 최악의 상황이 가장 느린 심사대에서 모든 사람이 심사를 받는 경우라
// int의 범위를 초과할 수 있어서 unsigned long으로 설정
// 실제로 long long 으로 했을 때 아래 소스코드에서는 틀렸었음
// 입력값 N 만큼 배열 동적할당
for (int i = 0; i < N; i++)
{
cin >> inspect[i];
if (max < inspect[i])
max = inspect[i];
//right값을 설정해주기 위해 입력을 받으면서 max 값을 갱신해줌
}
delete[] inspect;
// 동적할당 해제
(2) 이분 탐색 진행
unsigned long find_h(unsigned long left, unsigned long right, unsigned long inspect[], unsigned long N, unsigned long M)
{
unsigned long mid, cnt;
// 입국 심사를 몇명이 받았는 지 세는 변수 cnt 선언
// 이분 탐색을 진행할 중간값 변수 mid 선언
while (left <= right) // 이분탐색 종료 조건
{
mid = (left + right) / 2;
cnt = 0;
// 반복문이 돌면서 mid와 cnt 갱신
for (long i = 0; i < N; i++)
cnt += mid / inspect[i];
// 시간을 기준으로 확인한다.
// (ex) 20초 동안 한명을 6초에 심사할 수 있는 심사위원은 최대 3명까지 심사할 수 있다.
// 그래서 나머지 연산의 몫을 더하면서 cnt를 계산해준다.
if (cnt < M)
left = mid + 1;
else
right = mid - 1;
// 만약 인원이 전부 심사를 받았다면 시간을 줄여서 확인해보고
// 인원이 전부 심사를 받지 못했다면 시간을 늘려서 확인해본다.
}
return (left);
}
2-2. 풀이방법
예제 입력 1번의 경우를 설명해 본다면,
심사대의 시간은 각각 7초와 10초임
기본적으로 자리가 비었다면 바로 빈자리로 가는 것이 기본적으로 좋겠지만
두 심사대의 차이 3초보다 짧게 기다려서 빠른 심사대로 갈 수 있다면, 그 차이 만큼 시간의 이득을 볼 수 있음!!
3.코드설명
3-1. 이분 탐색
unsigned long find_h(unsigned long left, unsigned long right, unsigned long inspect[], unsigned long N, unsigned long M)
{
unsigned long mid, cnt;
while (left <= right)
{
mid = (left + right) / 2;
cnt = 0;
for (long i = 0; i < N; i++)
cnt += mid / inspect[i];
if (cnt < M)
left = mid + 1;
else
right = mid - 1;
}
return (left);
}
cnt += mid / inspect[i] 가 핵심코드
대기시간을 계산하려고 하면 너무 어려움
총 걸리는 시간을 임의로 잡고 나눗셈 연산으로 이분탐색을 진행
ex) 10초가 걸린다고 한다면 6초는 무조건 한명을 받을 수 있고 3초는 3명을 받을 수 있음
so, 각 배열을 순회하면서 우리가 설정한 시간의 몫을 누적시켜서 M과 비교하여 M보다 크거나 같다면 시간을 줄이고
M보다 작다면 시간을 늘림
4.전체 소스 코드
#include <iostream>
#define fast ios::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
using namespace std;
unsigned long find_h(unsigned long left, unsigned long right, unsigned long inspect[], unsigned long N, unsigned long M)
{
unsigned long mid, cnt;
while (left <= right)
{
mid = (left + right) / 2;
cnt = 0;
for (long i = 0; i < N; i++)
cnt += mid / inspect[i];
if (cnt < M)
left = mid + 1;
else
right = mid - 1;
}
return (left);
}
int main()
{
fast;
unsigned long N, M, max = 0;
cin >> N >> M;
unsigned long * inspect = new unsigned long[N];
for (int i = 0; i < N; i++)
{
cin >> inspect[i];
if (max < inspect[i])
max = inspect[i];
}
cout << find_h(0, max * M, inspect, N, M);
delete[] inspect;
return (0);
}
