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

전형적인 이분탐색의 lower_bound 형태이다.

 

전체적인 스켈레톤은 다음과 같다.

자세한 설명은 viyoung.tistory.com/77?category=284521 참고

// Lower_bound (이분탐색에서의 하계를 구하는 방법)

int start = 0;
int end = vector_container.size();

while (start < end){
    mid = (start + end) / 2;
    
    if(card[mid] < compare_value){
        start = mid + 1;
    }
    
    else{
        end = mid;
    }
}

사실 이 문제는 오버 플로우 때문에 개고생했다..

처음에는 end값을 리터럴로 잡으려고 하다가 계속 틀려서 input값을 기준으로 최댓값을 보정하니까 맞았다.

(생각보다 숫자가 엄청 크게 들어오는 것 같다.)

 

#include <iostream>
#include <vector>
#include <algorithm>
typedef unsigned long long ll;

using namespace std;

int main(void){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    ll N, M;
    cin >> N >> M;

    vector<ll> data_store(N, 0);

    for(int i = 0; i < N; i++){
        cin >> data_store[i];
    }
    sort(data_store.begin(), data_store.end());

    ll start = 0;
    ll end = M * data_store.back() + 1;
    while(start < end){
        ll mid = (start + end) / 2;
        ll count = 0;
        for(int i = 0; i < N; i++){
            count += mid / data_store[i];
        }

        if(count < M) start = mid + 1;
        else end = mid;
    }

    cout << end << "\n";
    return 0;
}