[백준 15810번 / C++] 풍선 공장

이 문제를 처음 접할 때 바로 이분 탐색을 떠올려야한다. 

 

1. low는 0 으로 초기화를 하고 high 같은 경우엔 1,000,000,000,000으로 초기화한다 ( 스태프가 1명이고 풍선 하나를 만드는데 걸리는 시간이 1,000,000초가 걸릴 때 풍선 1000,000개를 만들 경우 )  
2. 최소시간을 구하기 위해서 high 값을 갱신하면서 해당 조건문 블록에서 mid 값을 result 변수에 저장해준다. 

#include <iostream>
#include <vector>
using namespace std; 
typedef long long ll; 
vector <int> v; 
int main() {
	int n, m; 
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		int a; cin >> a; 
		v.push_back(a); 
	}
	ll l = 0; 
	ll h = 1000000000000;
	ll result = 0; 
	while (l <= h) {
		ll mid = (l + h) / 2; 
		ll sum = 0; 
		for (int i = 0; i < n; i++) {
			sum += mid / v[i]; 
		}
		if (m <= sum) {
			result = mid;
			h = mid - 1; 
		}
		else {	
			l = mid + 1; 
		}
	}
	cout << result; 
}

15810번: 풍선 공장