월간 코드 챌린지 시즌3 / 금과 은 운반하기

#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;
}

반복 연산 처리 + 이진 탐색

 

역시나 해법공식을 찾는 게 아니다. 반복 수행이 답이다.