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

문제 요약

사람 수 ,입국심사관 수, 각 심사관이 한 명을 처리해줄 수 있는 배열(times)이 주어집니다. 모든 사람이 입국심사를 끝내는 데 걸리는 최소 시간은 얼마일까요??

놓치기 쉬운 부분

대기열의 맨 앞 사람이 놀고 있는 심사관이 있더라도 자신의 편의를 위해 좀 기다려도 일을 빨리 처리하는 사람한테 처리받을 수도 있긴하다.
그렇지만 문제는 모든 사람이 입국심사를 빨리 끝내는 것이 기준이다!

제한사항

1. 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
2. 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
3. 심사관은 1명 이상 100,000명 이하입니다.

아이디어

1. 제한 시간이 주어졌을 때 이 시간안에 모든 사람이 입국 심사를 받을 수 있는지를 certify하는 일은 쉽다.

   모든 심사대가 제한시간 동안 쉬지 않고 돌아갔을 때 몇 명을 심사할 수 있는지와 같은 문제이기 때문이다.
   참고로 이건 mod 연산을 통해 구할 수 있다.

2. 제한 시간의 범위에서 이분탐색을 하며 가능한 최소의 제한시간을 찾는다.

삽질

1. 시간이 (최대 사람수) x (가장 일처리가 빠른 심사관의 처리시간)
   = 10^(9) * 10^(9)만큼 걸릴 수 있다는 걸 의식해서 long long int로 잡아뒀는데 정작 함수에서 parameter는 int로 잡아서 자동 casting이 일어나 틀렸습니다가 떴었다.
2. 몇몇 테케에서 시간초과가 떴었는데
   원인은 max_time의 초기값을 (최대 사람수) x (가장 일처리가 느린 심사관의 처리시간)으로 잡아서 1초만에 처리할 수 있는 수사관이 있더라도 그를 쓰지 않아 시간 후보 범위가 엄청 컸다는 점이었다.
3. 사실 이 문제 분류가 이분탐색이라고 써있어서 혼자 힘으로 풀 수 있었던 거고... 없었다면 못 풀었을지도 ^_ㅠ

코드

#include <string>
#include <vector>
#include<math.h>
#include<algorithm>
#include<iostream>
using namespace std;
//일단 시간 초과는 이제 안남
bool certify(int n,long long int in_time, vector<int> &times){//n명을 in_time안에 처리할 수 있는지를 검사
   long long int max_people = 0;// 각 검사대에서 intime안에 처리할 수 있는 사람의 수를 합산
   //근데 합산되다보니 int 넘어가기도함
   for(int i = 0;i<times.size();i++){
       max_people+= in_time/times[i];
   }
   //cout<<in_time<<","<<max_people<<endl;
   return max_people>=n;
}
long long int bin_search(long long int s, long long int e, int n, vector<int> times){
   if(e<s){
       return -1;
   }
   long long int m = (s+e)/2;
   bool certify_res = certify(n,m,times);
   //cout<<s<<","<<e<<","<<m<<","<<certify_res<<endl;
   if(certify_res){
       long long int child_res = bin_search(s,m-1,n,times);
       if(child_res == -1){
           return m;
       }
       else{
           return child_res;
       }
   }
   else{
       return bin_search(m+1, e,n,times);
   }
}

long long solution(int n, vector<int> times) {
   long long answer = 0;
   long long max_time = n* *min_element(times.begin(),times.end());
   cout<<max_time<<endl;
   long long min_time = 0;
   //max t, min t간 바이너리 서치
   answer = bin_search(min_time, max_time, n, times);
   return answer;
}