백준 15810번: 풍선 공장 (C++)

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

15810번: 풍선 공장

 

풀이

간단하지만 타입에 조금 신경써야 하는 이분 탐색 문제.

 

걸리는 시간을 줄여가며 몇 개의 풍선이 만들어졌는 지 체크한다.

우선 반복문을 돌며 걸리는 시간 (mid) / 스태프의 풍선 제작 시간 (v[i]), 즉 스태프가 만든 풍선의 갯수를 cnt에 더해주었다.

그리고 cnt 가 만들어야하는 풍선의 갯수 (M)보다 많다면 true를 반환시켜서 걸리는 시간을 줄이고 다시 탐색을 진행시켰다.

 

전체 코드

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

int N, M;
vector<int> v;

bool is_possible(long long mid) {
	long long cnt = 0;
	for (int i = 0; i < N; i++) cnt += mid / v[i];

	if (cnt >= M) return true;
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		int a;
		cin >> a;
		v.push_back(a);
	}

	long long left = 1, right = 1e15, ret = -1;

	while (left <= right) {
		long long mid = (left + right) / 2;
		if (is_possible(mid)) {
			ret = mid;
			right = mid - 1;
		}
		else left = mid + 1;
	}

	cout << ret;
}