[알고리즘/C++] 프로그래머스 - 입국심사 (Lv.3, 이분탐색)

🖋️ 이분탐색(이진탐색) 개념

• https://velog.io/@kimdukbae/%EC%9D%B4%EB%B6%84-%ED%83%90%EC%83%89-%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-Binary-Search
• 정렬된 리스트의 탐색 범위를 절반씩 줄여가며 데이터를 탐색하는 방법.
• 구현시 start/end/mid 혹은 min/max/avg 를 사용해 중간에 위치한 데이터를 반복적으로 비교한다.

✏️ 풀이 방법
min : 1명이 1분(문제에서 주어진 최소시간) 걸리는 심사관한테 받을 때
max : n명이 전부 가장 오래걸리는 심사관한테 받을 때
를 사용해서 금방 풀긴 했는데, 결국 자료형에서 많이 헤맸다.
'어차피 자동으로 형변환이 이루어질텐데' 하는 안일한 생각을 하다 이 답변을 보고 정신차렸다.
요즘 가장 기본적인 것들을 깜빡하는 때가 많아진 것 같다.

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;

    sort(times.begin(), times.end());

    long long minTime = 1;
    long long maxTime = (long long)times.back() * n;

    while (minTime <= maxTime)
    {
        long long avgTime = (minTime + maxTime) * 0.5;

        long long tmpN = 0;
        for (int i = 0; i < times.size(); ++i)
        {
            tmpN += avgTime / (long long)times[i];
        }

        if (tmpN >= n)
        {
            answer = avgTime;
            maxTime = avgTime - 1;
        }
        else
        {
            minTime = avgTime + 1;
        }
    }

    return answer;
}