알고리즘/programmers
월간 코드 챌린지 시즌3 / 금과 은 운반하기
유이얼
2022. 12. 10. 03:52
#include <string>
#include <vector>
#include <queue>
using namespace std;
using vi = vector<int>;
vi g_, s_, w_, t_;
int a_, b_;
bool f(long long t) {
int n = g_.size();
long long a = 0, b = 0, c = 0;
for (int i = 0; i < n; ++i) {
long long q = t / t_[i];
q = (q + 1) / 2;
long long capacity = q * w_[i];
a += min((long long) g_[i], capacity);
b += min((long long) s_[i], capacity);
c += min((long long) (g_[i] + s_[i]), capacity);
}
if (c < a_ + b_) return false;
if (a < a_ || b < b_) return false;
return true;
}
long long solution(int a, int b, vector<int> g, vector<int> s, vector<int> w, vector<int> t) {
g_ = g, s_ = s, w_ = w, t_ = t;
a_ = a, b_ = b;
long long left = 0;
long long right = 4E14;
while (left < right) {
long long m = (left + right) / 2;
if (f(m)) right = m;
else left = m + 1;
}
return right;
}
반복 연산 처리 + 이진 탐색
역시나 해법공식을 찾는 게 아니다. 반복 수행이 답이다.