이분 탐색

나중에 기억하기 쉽게 최대한 심플하게 정리

 

1. 먼저 가능한 answer의 범위의 최대값과 최소값을 구한다.

-> min, max

 

2. start 와 end를 초기화 + mid도 초기화

-> 당연히 처음에는 start = min, end = max

-> mid = (min+max)/2

 

3. while문을 사용, 루프 조건은 while( start<=end )

 

4. mid와 찾고자 하는 target을 비교

mid == target : 정답

mid < target : start = mid+1

mid > target : end = mid - 1

 

사용 예제

프로그래머스 입국 심사

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

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

 

구해야하는 것 : 모든 사람이 심사받는 최소 시간

 

풀이

1) 심사 받는 최소시간 최대시간 초기화

최소 시간 : 1

최대시간 : 가장 오래걸리는 사람한테 n명이 모두 심사 받을때

 

2) mid시간에서 실제로 가능한지 여부를 판단

-> 불가능할 수 도 있음

-> min = mid+1

 

3) mid에서 가능한 경우, answer와 비교하여 최솟값인지 판단.

-> max = mid-1

 

 

#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(int i=0;i<times.size();i++)
        {
            sum += mid /(times[i]);
        }
        
        if(sum >= n)
        {
            if(answer > mid)
                answer = mid;
            max = mid-1;
        }
        // 불가능 -> 시간을 더 많이
        else{
            min = mid+1;
        }
            
    }
    return answer;
}