[알고리즘] 백준 15810번: 풍선 공장 (C++)

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

15810번: 풍선 공장

결괏값의 자료형을 고민해본다면 풀 수 있는 이분 탐색 문제였다.

>> 한 사람이 한 풍선을 불 때 걸리는 시간이 1000000이라면 불어야 할 풍선의 개수가 1000000개 일 때를 고민해보면 된다.

#include <iostream>
#include <vector>
#include <climits>
#define ull unsigned long long
using namespace std;

vector<int> v;
int n, m;

int main(){
    cin >> n >> m;
    
    for(int i = 0, a; i < n; i++){
        cin >> a;
        v.push_back(a);
    }
    
    ull result;
    ull low = 0;
    ull high = 1000000000000;
    
    while(low <= high){
        ull mid = (low + high) >> 1;
        
        ull balloon = 0;
        for(int i = 0; i < v.size(); i++){
            balloon += mid / v[i];
        }
        
        //cout << mid << ' ' << balloon << '\n';
        
        if(balloon >= m){
            result = mid;
            high = mid - 1;
        }
        else{
            low = mid + 1;
        }
    }
    
    cout << result;
    return 0;
}