백준 15810번: 풍선 공장 (C++)
2023. 1. 23. 21:41ㆍ알고리즘/이분탐색
https://www.acmicpc.net/problem/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;
}
'알고리즘 > 이분탐색' 카테고리의 다른 글
백준 6236번: 용돈 관리 (C++) (0) | 2023.01.23 |
---|---|
백준 11663번: 선분 위의 점 (C++) (0) | 2023.01.23 |
백준 1590번: 캠프가는 영식 (C++) (2) | 2023.01.23 |
백준 20551번: Sort 마스터 배지훈의 후계자 (C++) (0) | 2023.01.23 |
백준 17266번: 어두운 굴다리 (C++) (1) | 2023.01.21 |