[백준/c++] 3027번 입국심사 (Binary Search)

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

3079번: 입국심사

0. 잡담

아이고 로직은 맞았는데 입력 범위가 매우 커서 7트만에 맞았습니다!!를 받았습니다.
만약 알 수 없는 문제로 10%에서 계속 틀리신다면 코드의 모든 부분에 마음 편하게 unsigned long long 자료형을 써보세요.
혹시 답을 보고  푸셨다면 이곳에서 다시 풀어보시면 좋을 것 같습니다. 동일한 문제에 입력 값이 백준보다 작습니다.

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

프로그래머스

이분탐색에 대해 제가 느낀 점입니다.
어떤 문제를 마주했을 때 이 문제가 이분탐색으로 풀이가 가능한지 느끼기 어려운 것 같습니다.
이분탐색의 left, right를 조여가는 원리에만 집중하면, 주어진 input array에 이분 탐색을 적용해야만 하는 느낌이 듭니다.

하지만 이렇게 하면 난이도가 높은 대부분의 문제를 풀기 어렵습니다.

이분탐색은 주어진 array 안에서 좁혀가면서 찾는 것이 아니라, 주어진 범위에서 나올 수 있는 최솟값과 최댓값 사이에서 범위를 좁혀가며 mid가 주어진 array에서 적용될 수 있는지 체크하는 것이 중요한 것 같습니다.

1. 범위가 넓고 어떤 수가 문제의 답이 되는지 찾아야 할 때
2. 문제의 답이 최적의 수를 원하는 경우
3. 뭔가 브루트 포스로도 풀 수 있을 것 같은데 시간 초과가 염려될 때
이분 탐색을 활용하면 좋을 것 같다는 생각을 했습니다.

이분 탐색은 밑이 2인 log n 이므로, 10억개의 수 중 하나를 찾아야 할 때 약 30번의 탐색을 하므로 시간 초과의 염려가 없습니다.
(바꿔 말하면 숫자의 범위가 매우 커서 킹받게 overflow가 많이 납니다)

1. 접근

위에서 언급했듯이, 주어진 Tk에서 최적의 순서를 정하는 방법 보다는,
어떤 시간이 주어졌을 때 그 시간안에 몇명의 사람이 입국심사를 받을 수 있는지 확인하는 방법이 유효합니다.

1번 예제를 예를 들면,
30초에는 30 / 7 = 4, 30 / 10 = 2 --> 6명이 입국 심사를 받을 수 있어 답이 될 수 있습니다.
또한, 28초에도 28 / 7 = 4, 28 / 10 = 2 --> 6명이 입국 심사를 받을 수 있어 답이 될 수 있습니다.
답은 최적의 값이 28초가 될 것입니다.

다시 생각해봅시다.
최소의 시간, 그러니까 Left는 1초가 될 것입니다.
최대의 시간, 그러니까 Right는 (입력된 숫자 최댓값 * m)이 될 것입니다.
가장 시간이 오래 걸리는 입국심사대에만 줄을 서서 아주 비효율적인 경우로 심사를 받는 경우입니다.

10억개의 숫자에서 탐색을 해도 최악의 경우에 30번 탐색을 진행하므로 범위를 넓게 넓게 설정해줍니다.

그러면 예제 1의 경우 다음과 같이 탐색을 진행할 수 있습니다.

15초가 주어진 경우에는 3명만 심사가 가능합니다. 6명이 심사를 받아야 하므로 시간초를 늘리기 위해 left를 mid+1해줍니다.

23초가 주어진 경우에는 5명이 심사가 가능합니다. 6명이 심사를 받아야 하므로 시간초를 늘리기 위해 left를 mid+1해줍니다.

27초가 주어진 경우에도 5명만 심사가 가능합니다. left = mid+1을 해줍니다.

드디어 6명이 식사가 가능한 시간초인 29를 찾았습니다! 답에 29를 기록해줍니다.

하지만 아직 탐색이 끝나지 않았습니다. right = mid-1을 해주어 끝까지 탐색해봅시다.

이번에도 6명의 심사가 가능하고, 이전 답인 29보다 작은 값인 28초를 발견했으므로 답에 28을 기록해줍니다.

이후에는 right가 left보다 작아지므로 최종 답인 28이 됩니다.

3. 코드로 옮기기

//
//  입국심사.cpp
//  Problem_Solving
//
//  Created by joonhwi on 2023/01/25.
//

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

int n, m;
vector<unsigned long long> v;


void input(){
    cin>>n>>m;
    v.resize(n);
    
    for(int i=0; i<n; i++){
        cin>>v[i];
    }
    
    sort(v.begin(), v.end());
}

void find_ans(){
    unsigned long long start = 0;
    unsigned long long end = v.back()*m;
    unsigned long long ans= 1000000000000000001;
    
    while(start <= end){
        unsigned long long mid = (start+end)/2;
        
        unsigned long long cnt = 0;
        for(int i=0; i<n; i++){
            cnt += mid/v[i];
        }
        
        if(cnt < m) start = mid + 1;
        else {
            ans = min(ans, mid);
            end = mid - 1;
        }
    }
    
    cout<<ans;
    return;
}

void solve(){
    input();
    find_ans();
    
    return;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    solve();
    
    return 0;
}