[BOJ/C++] 3079: 입국심사

🏅 Gold 5

✏️ 1차 솔루션

1. 입국심사 시간은 오름차순 정렬
2. 최소 입국심사 시간을 기준 시간으로 설정
3. 기준 시간의 1, 2, 3 ... n 배를 해보면서 해당 시간일 때 각 심사대가 받을 수 있는 사람을 count
   ➡️ 해당 시간에서 각 심사대가 받을 수 있는 사람 = (해당 시간) / 각 심사대 심사 시간

🚨 1차 trouble

반례 테케까지 다 맞는데 왜 틀리는지 모르겠다..

✏️ 최종 솔루션

⭐️ 이분 탐색 풀이
기존 풀이에서 기준 시간을 n 배 해보면서 최적시간을 찾는 과정을 이분탐색으로 변경

⭐️ left = 1 , right = 최소 심사 시간 * 인원수(m)

1. 반복할 때마다 mid 값을 갱신해줘서 mid 에서 심사할 수 있는 인원을 구하기
2. 심사할 수 있는 인원이 전체 인원수보다 적으면 left = mid + 1 로 바꿔줘서 mid 이후의 범위를 탐색하도록 범위 좁혀주기
3. 심사할 수 있는 인원이 전체 인원수보다 크거나 같으면 answer 에 저장해두고 right = mid - 1 로 바꿔줘서 mid 이전의 범위를 탐색하도록 범위 좁혀줘서 최소값 계속해서 탐색

📌 self feedback

이분 탐색을 어떻게 적용해야할지 모르겠을 때는 탐색의 범위를 어떻게 규정지을까를 먼저 생각하면 hint 얻을 수 있을 듯
가장 작은 입국심사 시간에서 n 배를 계속 더해가면 탐색 범위가 너무 넓어지는데 이분 탐색을 적용하면 범위를 축소할 수 있고 최소 입국심사 시간 * 인원수(m) 을 최대값으로 설정하면 그 범위를 더욱 축소할 수 있음
❗️ 왜 때문인지 모르겠지만 이 문제에서 최대 입국심사 시간 * 인원수(m) 을 최대값으로 설정하면 틀리다고 함;;

✏️ 최종 code

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

int main() {
    int n,m;
    cin >> n >> m;
    
    vector<long long> t;

    for(int i=0;i<n;i++) {
        long long k;
        cin >> k;
        t.push_back(k);
    }
    
    sort(t.begin(),t.end());
    
    long long ans=0;
    long long left=1;
    long long right=t[0]*m;
    
    while(left<=right) {
        long long mid=(right+left)/2;
        
        long long sum=0;

        for(int i=0;i<n;i++) {
            sum+= (mid/t[i]);
        }
        
        if(sum<m) {
            left=mid+1;
        }
        else {
            ans=mid;
            right=mid-1;
        }
        
    }
    
    cout << ans << endl;
}