입국심사 (feat. 프로그래머스, 43238번)

입국심사
https://programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

반응형

// woohyeon.kim
#include <vector>
#include <algorithm>

using namespace std;
 
long long solution(int n, vector<int> times) {
    sort(times.begin(), times.end());
    long long answer = 0;
    long long min_time = 1;
    long long max_time = times.back() * static_cast<long long>(n);
    while (min_time <= max_time)
    {
        long long human = 0;
        auto mid_time = ((max_time + min_time) / 2);
        for (const auto& t : times)
        {
            auto value = mid_time / t;
            human += value;
        }
        if (n <= human)
        {
            answer = mid_time;
            max_time = mid_time - 1;
        }
        else
        {
            min_time = mid_time + 1;
        }
    }
    return answer;
}
// *&)*@*

Binary Search를 사용하되, n과 human이 같으면 return되지 않고 계속해서 min_time/max_time을 맞춰가는게 포인트입니다.