[백준][3079번][이분탐색] 입국심사

입국심사

https://www.acmicpc.net/problem/3079

<코드>

#include <stdio.h>
 
long long T[1000001];
 
int main(void){
 
    int N, M;
    long long max = 0;
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < N; i++){
        scanf("%lld", &T[i]);
        if (max < T[i])
            max = T[i];
    }
 
    long long left=1, right=max*M;
    long long result = max*M;
    while (left <= right){
        long long mid = (left + right) / 2;
        long long total = 0;
        for (int i = 0; i < N; i++)
        {
            total += mid / T[i];
        }
 
        if (total < M){
            left = mid + 1;
        }
        else{
            if (result>mid)
                result = mid;
            right = mid - 1;
        }
    }
    printf("%lld\n", result);
 
    return 0;
}

<문제 푼 요령>

 1. 마찬가지로 유추한 정답값으로 -> 문제에 대입해 봐서 정답을 구하는데 유추를 할때 이분 검색을 사용하였다.

 2. 여기서 만약 최종 걸린 시간을 안다면 반대로 몇명이 지나갈 수 있는지 알 수 있다.

 3. 그래서 그 지나간 사람이 M보다 크거나 같다면 이걸 저장하고 이것보다 낮은값이 있나 검색을 한다. 

 4. 그렇게해서 나온 최소값이 정답이 되는 것이다.