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

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

프로그래머스

 

로직

총 심사시간 / 심사 시간(단건) = 심사한 사람 수

 

이진탐색으로 총 심사시간의 최소값을 찾을 수 있는 이유

이진탐색은 주어진 조건(심사 시간)내에서 가능한 최적의 해(총 심사시간의 최소값)을 찾는 방법이다.

=> 총 심사 시간을 늘이고, 줄이면서 결국 총 심사시간의 최소값을 반환한다.

 

이진탐색

1. 탐색 범위 올바르게 설정

답이 될 수 있는 상한(최대 범위), 하한(최소 범위)를 설정하고, 중간값은 (상한+하한)/2이다.

 

2. 중간점(mid)를 기준으로 탐색 조건 만족하는지 확인

탐색 결과에 따라 상한과 하한을 조절한다.

📌 반복되는 뺄셈은 나눗셈으로 한번에 처리 가능하다 ( mid - t - t - t ... - t = mid / t )

 

코드

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
ll maxtime;

long long solution(int n, vector<int> times) {
    long long answer = 0;
    //1. 최대 시간 구하기
    for (ll t:times) maxtime = std::max(t, maxtime);
    //2. 이진탐색 수행하기
    ll l=0, r=maxtime*n, mid=0;
    answer = maxtime*n; //최소 시간을 구하므로 최대 시간부터 시작
    while (l<=r){
        mid = (l+r)/2;
        ll member=0;
        for(int t:times) member += mid / t;
        if(member>=n){
            answer = min(answer, mid);
            r = mid-1;
        } else l=mid+1;
    }
    
    return answer;
}