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

 

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

코딩테스트 연습 - 입국심사

코드 설명 

시간 이라는 개념을 이분탐색으로 찾아야 한다는게 포인트이다.

최소값은 1분 ~ 최대값은 times가 가진 최대 시간 * n(사람수) 이다.

그 후, mid시간 동안 몇명을 검사 할수 있는지 cnt를 통해 구한다. ( 구하는 법은 시간/times[i])

 

또한 최대값을 설정할때 long long 설정에 유의하자!

long long endd=n*(long long)times[k-1];

 

코드

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    //입국심사 사람 1,000,000,000 => longlong 이분탐색 생각!
    sort(times.begin(),times.end());
    long long k=times.size();
    long long startt=1;
    long long endd=n*(long long)times[k-1];
    long long cnt=0;
    
    
    while(startt <= endd){
    long long midd=(startt+endd)/2;
        cnt=0;
     for(int i=0;i<k;i++){
        cnt += midd/times[i]; //시간당 심사인원한명이 심사할수 있는 인원수 합
    }
       
        if(cnt<n){  // 불가능
            startt = midd+1;    
        }
        else{ //가능 
            //최소시간 구하기
            answer=midd;
            endd=midd-1;
        }
        
    
    }
    
    
    
    return answer;
}