[ SWEA 3074 ] 입국심사 (C++)

SWExpertAcademy의 입국심사(3074 / D4) 문제이다.

[ 문제풀이 ]

1) 모든 사람들이 입국심사를 받는데 걸리는 최소시간을 찾아야 하는 문제이다.

   먼저, 한명 한명 모든 사람을 심사를 받는 최소시간을 계산하면서 심사를 받게 한다면, 최악의 경우 최소

   10^9 만큼의 연산을 해줘야 한다. 즉, 이 수치만으로도 10개의 테스트 케이스를 합쳐서 1초 내에 통과하기 벅찰 것이다.

   따라서 본인은 '시간'에 대한 이분탐색을 진행해 주었다.

   이 문제에서 하나의 케이스가 주어졌을 때, 가장 오래 걸리는 시간은 몇초일까 ??

   아마, 심사대 중에서 심사 시간이 가장 오래 걸리는 심사대에 모든 사람이 들어가는 경우가 가장 오래 걸리는 시간일 것이다.

   예를 들어서 심사대가 3개가 있고, 각각의 심사대가 심사하는데 걸리는 시간이 [ 5 , 10 , 15 ] 초라고 가정해보자.

   그리고 사람이 10명을 심사를 받아야 한다. 가장 오래 걸리게 될 경우, 몇초일까 ??

   아마 15초짜리 심사대에 10명이 모두 들어가서 150초가 걸리는 경우가 가장 오래 걸리는 경우일 것이다.

   따라서, 이분탐색을 위해 계산되는 Left, Right값을 0초와, 위의 계산처럼 계산을 했을 때 가장 오래걸리는 시간을

   Right값으로 두고 탐색을 시작하였다. 왜냐하면, 답은 이 2개의 값 사이에 존재하기 떄문이다.

2) 그렇다면, 저 시간을 가지고 몇 명을 심사할 수 있는지를 알아보자.

   간단한 예를 한번 들어보자.

   심사대가 2개 , 각각 [ 3초 , 5초 ] 가 걸리고, 사람이 10명있다.

   그럼 만약, 8초에 시간이 주어졌다면 사람을 몇 명 심사할 수 있을까 ??

   아마, 3초 심사대에서는 2명을, 5초 심사대에서는 1명을 심사할 수 있다. 즉, 총 3명의 사람을 심사하게 된다.

   우리는 여기서 주어진 시간내에 몇 명의 사람을 심사할 수 있는지 알 수 있게 된다.

   심사 받을 수 있는 사람의 수 = 주어진 시간 / 심사대가 심사하는데 걸리는 시간

   이 된다. 물론 저기서 모든 심사대에 저 식을 적용시켜 모두 더해 주어야 한다.

   우리가 위의 예제에서,

   심사 받을 수 있는 사람의 수 = 8초 / 3초 + 8초 / 5초 라고 계산을 했듯이, 저렇게 모두 더해주어야 한다.

   이런식으로, M명을 만족시킬 수 있는 시간을 계속해서 찾아가는 이분탐색을 진행해주면 된다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define N_MAX 100005
typedef long long ll;
using namespace std;
 
ll Answer, Biggest_Time;
int N, M;
ll Counter[N_MAX];
 
void Initialize()
{
    Answer = 0;
    Biggest_Time = 0;
}
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        cin >> Counter[i];
        if (Counter[i] > Biggest_Time) Biggest_Time = Counter[i];
    }
}
 
void Solution()
{
    ll Left = 0;
    ll Right = (ll)(Biggest_Time * M);
    ll Mid, Sum;
    Answer = Right;
 
    while (Left <= Right)
    {
        Sum = 0;
        Mid = (Left + Right) / 2;
 
        for (int i = 0; i < N; i++)    Sum = Sum + (Mid / Counter[i]);
    
        if (Sum < M) Left = Mid + 1;
        else
        {
            Answer = Mid;
            Right = Mid - 1;
        }
    }
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}