[C++]이분탐색 입국심사(프로그래머스 3레벨)

 
#include <vector>
#include <algorithm>
 
using namespace std;
 
long long solution(int n, vector<int> times) 
{
    long long answer = 0;
    long long IMinTime = 1;
    long long IMaxTime = 0;
    long long lAvgTime = 0;
    long long lHuman = 0;
    IMaxTime = *max_element(times.begin(), times.end()) * (long long)n;
 
    while (IMinTime <= IMaxTime)
    {
        // 중간 시간 구하기
        lAvgTime = ((IMaxTime + IMinTime) / 2);
 
        // 중간 시간에 맞는 사람 수 구하기
        for (int i = 0; i < times.size(); ++i)
        {
            lHuman += lAvgTime / t;
        }

        // 맞는 사람 수가 인원수보다 많으면 정답 변경 + 최대 시간 변경
        if (n <= lHuman)
        {
            answer = lAvgTime;
            IMaxTime = lAvgTime - 1;
        }
 
        // 그게 아니라면 최저 시간 변경
        else    
            IMinTime = lAvgTime + 1;
 
        lHuman = 0;
    }
 
    return answer;
}

접근법을 잘 못 해서 오래 고민했다.

이분법으로 중간 값에서부터 계속 찾아야 했는데 아예 하나하나 찾아서 계산하려고 했던 게 실수였다.

하나하나 하기에는 여러 개의 심사관이 있어서 더 많은 문제가 생기기도 하지만 수가 매우 크기 때문에 하나하나 탐색하면서 가면 효율성에서 문제가 생긴다. 그래서 다른 방법으로 풀어야 했다.

 

그래서 찾게 된 것이 이분 탐색인데

제일 작은 값(제일 조금 걸리는 사람이 혼자 다하는 시간), 제일 큰 값(제일 오래 걸리는 사람이 혼자 다하는 시간)의 사이에 있는 값을 기준으로 이때

사람의 수가 더 많다면 더 많은 수를 처리할 수 있다는 말이기 때문에 최대 시간을 중간 시간에서 - 1 해서 풀어준다.

아니라면

사람의 수가 더 적은 수밖에 처리할 수 없다는 말이기 때문에 더 작은 수를 중간 값으로 해서 풀어준다.

이분 탐색은 계속 검색해야 하는 시간을 반으로 줄여가면서 탐색하는 방법!

구해야 하는 값이 너무 커서 반으로 잘라서 구하는 게 하나씩 구하는 것보다 빨라서 이분 탐색을 써야만 했던 거 같다.