[ 프로그래머스 입국심사 (Lv3) ] (C++)

프로그래머스의 입국심사(Lv3) 문제이다.

[ 문제풀이 ]

모든 경우의 수를 다 탐색해 보기에는 사람의 수도, 걸리는 시간도, 심사관의 수도 너무나도 값들이 크다.

그래서 이분탐색을 이용해서 탐색해 주었다.

탐색의 조건은 "시간이 T분 주어졌을 때, 주어진 n명이 모두 심사받을 수 있는지?" 이다. 즉 ! 시간을 크게도 만들어보고 작게도 만들어보면서, n명이 모두 심사받을 수 있는 최소의 시간을 찾는 것이다.

그럼 T분이 주어졌을 때, 각 심사대가 몇 명을 심사할 수 있는지부터 알아보자.

예를 들어서 심사대가 딱 1개가 있고, 이 심사대는 심사하는데 5분이 걸린다고 가정해보자.

그리고 주어진 시간이 10분이라고 가정해보자. 몇 명을 심사할 수 있을까 ?? 2명이다. 너무나도 쉬운 계산이다.

그럼 주어진 시간이 12분이라고 가정해보자. 몇 명을 심사할 수 있을까 ?? 2명이다. 어떻게 계산했는지는 모르겠지만 2명인 건 알 것 같다.

그럼 주어진 시간이 T분이라고 가정해보자. 몇 명을 심사할 수 있을까 ??

바로 "T / 5" 명이 된다. 하나 더 나아가보자. 심사대가 심사하는데 걸리는 시간이 x분이 걸린다. 그리고 T분이 주어졌을 때,

이 심사대에서는 주어진 시간동안 몇 명을 심사할 수 있을까 ?

심사 받을 수 있는 사람의 수 = T / x 명 !

이렇게 계산할 수가 있다.

하나만 더 나아가보자. 심사대가 3개가 있다. 각 심사대는 심사하는데 { a, b, c } 분이 걸린다고 가정하자.

그리고 시간이 T분이 주어졌다. 총 몇 명이 심사를 받을 수 있을까 ??

심사를 받을 수 있는 사람의 수 = T / a + T / b + T / c

위와 같이 계산을 할 수가 있다.

즉 ! 우리는 위와 같이 시간 T의 값을 이분탐색으로 탐색해보면서, 구체적으로는 "T분이 주어졌을 때, 심사를 받을 수 있는 사람의 수가 n명 이상인가?" 를 판단할 것이다.

그럼 이분탐색을 위해서는 초기 Start값과 End값(Left & Right값) 이 필요하다.

어떻게 설정해줄까 ?? 우리의 기준은 "시간" 이다.

Start의 값은 1분으로 설정해주자.

그럼 End의 값은 ?? 문제에 주어진 시간의 최댓값인 1000000000 분으로 설정해도 무관하지만 본인은 "주어진 입력에서 걸릴 수 있는 최대시간" 을 End 값으로 설정해 주었다.

예를 들어서 심사대가 3개가 있고, 각각의 심사대는 심사하는데 { 1, 2, 3 } 분이 걸린다고 가정해보자.

그리고 사람 10명이 심사를 받아야 하는 상황이다. 최악의 경우, 즉 심사를 하는데 가장 오랜 시간이 걸리게 심사를 받게 만들려고 한다면 몇 분이 걸릴까 ??

10명 모두 3분이 걸리는 심사대에서만 심사를 받게하면 가장 오랜시간이 걸리게 만들 수 있다.

즉 ! 3 x 10 = 30분이 위의 케이스에서 심사를 하는데 가장 오래 걸릴 수 있는 최대시간 이 된다.

위와 같이, 주어진 입력에서 "심사하는데 가장 오래걸리는 심사대의 시간 x 사람의 수" 를 End 값으로 설정해 주었다.

이 후, 이분탐색에서는 위에서 이야기했던 "심사를 받을 수 있는 사람의 수"를 계산하면서 정답을 찾아주었다.

[ 소스코드 ]

#include <string>
#include <vector>
 
using namespace std;
 
long long Binary_Search(long long Mid, vector<int> T)
{
    long long Result = 0;
    for (int i = 0; i < T.size(); i++)
    {
        Result = Result + (Mid / T[i]);
    }
    return Result;
}
 
long long solution(int n, vector<int> times) 
{
    long long Start = 1;
    long long End = 0;
    long long Temp = 0;
    for (int i = 0; i < times.size(); i++)
    {
        if (Temp < times[i]) Temp = times[i];
    }
    End = Temp * n;
    while(Start <= End)    
    { 
        long long Mid = (Start + End) / 2;
        if (Binary_Search(Mid, times) < n) Start = Mid + 1;
        else End = Mid - 1;
        
    }
    return Start;
}