백준/이분탐색
[백준 15810번 / C++] 풍선 공장
배발자
2022. 2. 16. 01:28
반응형
이 문제를 처음 접할 때 바로 이분 탐색을 떠올려야한다.
- low는 0 으로 초기화를 하고 high 같은 경우엔 1,000,000,000,000으로 초기화한다 ( 스태프가 1명이고 풍선 하나를 만드는데 걸리는 시간이 1,000,000초가 걸릴 때 풍선 1000,000개를 만들 경우 )
- 최소시간을 구하기 위해서 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;
}
반응형