[ 프로그래머스 C++ ] 입국심사 lv3

< 해설 >

코딩테스트 고득점 Kit 안에 있는 이분탐색 문제이다. 이분 탐색 문제는 처음 풀어보기 때문에 이분탐색이란 어떤 것인가를 먼저 공부했다. 원리는 간단하다. 반씩 갈라서 크면 위쪽을 탐색, 작으면 아래쪽을 탐색하는 방법이다. 이를 적용하기 위해서는 데이터가 정렬이 되어있어야 한다는 것을 느낌적으로 알 수 있다!

 

다시 문제 해설로 넘어오면, n명이 입국심사를 진행하는데 가장 오래 시간이 걸리려면 입국심사 시간이 긴 한 사람에게 모두 입국심사를 받는 것이다. 따라서 n * (가장 입국 심사 시간이 긴 사람) 이 최대 maximum 값이 된다. 이를 가지고 하나씩 비교를 해주면 된다!

 

테스트 케이스에서는 n 이 6이고 7분/10분 으로 입국심사가 진행되므로 맥시멈 시간(end 시간)은 60분이 될 것이다. 1과 60사이의 반절이면 30이 되고 다음 비교는 1과 30의 반절인 15가된다. 15분만에 6명의 입국심사를 진행할 수는 없으므로 16 -  29 사이에서 답을 찾게 될 것이다. 검사를 진행하다가 사이값을 비교하는 처음 수와 마지막 수가 같아지면 그게 답이 된다.

그런데 어떤 식으로 최소로 일을 진행하게 되나요? 라는 생각이 드는데 이는 범위에서 뽑은 중간값을 입국 심사 시간으로 나누었을 때의 몫을 누적해보면 된다. 누적값이 n 보다 크면 end 시간을 줄이고 누적값이 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 start = 1;
    long long end = (long long)times[times.size() -1] * n;
    
     while(start <= end)
     {
        long long mid = (start + end) / 2;
        long long cnt = 0; 
        for(int i=0; i<times.size(); i++)
        {
            cnt += mid / times[i]; 
        }

        if(cnt < n)
        {
            start = mid + 1;
        }
        else
        {
            answer = mid;
            end = mid - 1;
        }
    }
    
    return answer;
}