[백준] 3079번 입국심사 C++ 코드

코드

#include <iostream>

using namespace std;
typedef long long ll;
ll n, m, a[100003], s, e = 1e18,result,temp;
int main() {
    cin >> n >> m;
    for(ll i = 0; i < n; i++) cin >> a[i];
    
    while(s <= e) {
        ll mid = (s + e) / 2;
        temp = 0;
        for(ll i = 0; i < n; i++) {
            temp += mid / a[i];
            if(temp >= m) break; // 이 부분이 없으면 틀렸습니다, 오버플로우 때문인 듯
        }
        if(temp < m) {
            s = mid + 1;
        } else {
            result = mid;
            e = mid - 1;
        }
    }
    cout << result << '\n';
    return 0;
}

시간을 줄이고 늘리는 방식으로 최소값을 찾아주면 되는데, if(temp >= m) break; 부분을 넣어주지 않아서 헤맨 문제. a[i]값이 작고 mid 값이 큰 경우, mid / a[i] 값이 큰 값을 갖는데 이를 여러 번 더하면 temp가 long long의 범위를 넘어서게 된다. 그래서 최적화를 해주기 위해 저 코드가 필요