백준 3079 - 입국심사 - 이분 탐색

문제

문제링크 : https://www.acmicpc.net/problem/3079

풀이전략

1. long long을 사용하는 것이 매우 중요하다. 값이 크다.
2. 사실상 시간에 따라 넘어갈 수 있는 심사대에 인원수를 구하면 된다.
3. 시간이 이분 탐색할 부분이다.

코드

#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;

long long N, M;
vector<long long> desk;
long long checkTime(long long time){
    long long ret = 0;
    for(int i=0; i<desk.size(); i++){
        ret = ret + (time / desk[i]);
    }
    return ret;
}

long long res = 1e18;
long long BinarySearch(long long lt, long long rt){
    if(lt > rt){
        return res;
    }
    else{
        long long mid = (lt + rt) / 2;
        long long midVal = checkTime(mid);

        if(midVal >= M){
            if(res > mid) res = mid;
            return BinarySearch(lt, mid-1);
        }
        else{
            return BinarySearch(mid+1, rt);
        }
    }
}

int main(){

    // freopen("../input.txt","rt",stdin);

    scanf("%lld %lld",&N, &M);

    long long tmp = 0;
    // long long mmin = 2147000000;
    for(int i=0; i<N; i++){
        scanf("%lld",&tmp);
        // if(tmp < mmin) mmin = tmp;
        desk.push_back(tmp);
    }
    sort(desk.begin(), desk.end());
    // printf("%lld\n",BinarySearch(1, mmin*M)) ;
    printf("%lld\n",BinarySearch(1, desk[N-1]*M)) ;
    return 0;
}

// 틀린이유 1 : 출력시 long long 이면 print도 lld로 해주기
// 틀린이유 2 : long long type을 반환시키는 것이면 long long으로 적어주어야 한다. 
// 틀린이유 3 : long long의 경우 최대값을 10^18으로 잡자 1e18

소감

이 문제에서 다양한 이유로 틀렸는데 먼저 long long type은 print해줄때 lld로 써줘야한다. 또한 long long type을 반환시킬 때는 long long type을 적어줘야한다. 마지막으로 long long type의 최대값은 10^18이다 이 부분이 매우 중요하다.

long long의 최대값은 1e18이라고 적고 사용하면 된다.