programmers 입국심사 c++

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

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

level3 입국심사 문제입니다.

이분탐색을 이용하는 대표적인 문제라길래 풀어봤습니다.

 

이분탐색은 기본적으로 어떤 값을 기준으로 이분탐색을 할 것인지 파악하는게 중요합니다.

그걸 찾기가 정말 어려운데,

이번 문제는 애초에 '시간의 최솟값을 반환' 이라는 말에서 시간을 기준으로 이분탐색을 진행하라는게 주어져있습니다.

 

이분탐색의 조건을 찾았으면, 이 탐색간의 범위를 지정하는 기준이 무엇인지 파악해야하는데,

이 문제에서는 '현재 시간'으로 모든 사람들을 심사할 수 있는지 파악해야 합니다.

간단하게, 모든 심사위원의 심사시간을 '현재 시간'으로 나누어서 심사할 수 있는 모든 사람을 찾은 후에,

주어진 n과 비교해서 탐색을 진행해주시면 됩니다.

 

이분탐색 연습하기에는 좋은 문제인 것 같습니다.

#include <string>
#include <vector>

using namespace std;
using ll = long long;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    long long s = 1;
    long long e = (ll)100000000*n;
    long long m;
    while(s<=e){
        m = (s+e)/2;
        ll person = 0;
        for(auto time : times) person += m/time;
        
        if(person >= n) e = m-1, answer = m;
        else s = m+1;
    }
    
    return answer;
}