프로그래머스_입국심사

문제 : https://programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사 | 프로그래머스

처음에는 해당 문제가 왜 이분탐색인지 조차도 이해가 가지 않았다.

완전탐색으로 하면 주어진 문제조건 10억에 의해 터질 것은 예상했지만 이분 탐색은 이해가 가지 않았다.

추정 시간값/ 각 심사관별 심사시간 = 심사관당 맡을 수 있는 입국자 수

그런데, 다음의 공식을 이해하는 순간 이분 탐색 문제임을 이해하였다.

시간을 기준으로 특정 시간을 주고 그 시간에 해결이 가능한지를 검사한 다음 이분 탐색으로 가능한 시간 찾기!

전체 걸리는 추정 시간 값을 각 심사관별 심사시간으로 나누어주게 되면 심사관당 맡은 입국자 수가 나오게 되고 이를 다 더해서 원래 주어진 입국자 수를 감당가능한지를 계산하는 알고리즘으로 해결이 가능하였다.

그 과정에서 변수들을 long long 처리해야 하는 것을 명심해야 한다!

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

using namespace std;

long long solution(int n, vector<int> times) {
    int s = times.size();
    sort(times.begin(), times.end()); 
    long long min =1;
    long long max = (long long)(times[s-1]) * n; 
    long long answer = max;
    
    // 이진 탐색
    while(min<=max){
        long long mid = (min+max)/2;
        long long sum=0;
        for(int i=0;i<s;i++)
            sum += mid/times[i]; // 한 심사관당 담당 수
        // n과 비교
        if(n>sum) min = mid+1;
        
        // 가능한 경우
        else {
            if(mid <= answer)
                answer = mid;
            max = mid-1;
        }
    }
    return answer;
}

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

using namespace std;

long long solution(int n, vector<int> times) {
    sort(times.begin(), times.end());
    long long min = 1;
    long long max = (long long)(times[times.size()-1])*n;
    long long answer = max;
    
    // 이분 탐색으로 찾을 때 까지
    while(min<=max){
        // mid 는 총 걸린 시간
        long long mid = (min + max)/2;
        long long sum = 0;
        
        // 심사위원당 맡을 수 있는 사람 수 더하기
        for(vector<int>::iterator iter = times.begin(); iter != times.end(); iter++){
            sum += mid /(*iter);
        }
        
        // 가능
        if(sum >= n){
            // 값 비교
            if(answer > mid)
                answer = mid;
            // 가능 -> 시간 줄여보기(최대 가능 경우)
            max = mid-1;
        }
        // 불가능 -> 시간을 더 많이
        else{
            min = mid+1;
        }
            
    }
    return answer;
}