[BOJ 21257] Fireworks

백준 문제 링크

🔍 문제 분석

• 본 문제에서는 성공할 때까지 폭죽을 제작하고 테스트하는 과정을 반복한다. 폭죽의 개수와는 관계없이 현재 시점까지 만들어진 모든 폭죽을 테스트하는데 걸리는 시간은 m이다. 따라서, 매번 num개의 폭죽을 제작하고 테스트한다고 가정한 후 예상 시간을 최소화하는 x를 탐색한다.
• 테스트의 성공은 확률적으로 결정되므로 예상 시간은 테스트의 성공확률의 기댓값과 폭죽을 제작하고 테스트하는데 걸리는 시간의 곱으로 나타낼 수 있다. 이 과정은 테스트가 성공할 때까지 반복되므로 기하 분포를 따른다는 것을 알 수 있다. 수식으로 나타내면 다음과 같다.

\[P(X = x) = 1 - (1 - p \times 10^{-4})^x\] \[E(X = x) = \frac{1}{P(X = x)} = \frac{1}{1 - (1 - p \times 10^{-4})^x}\] \[\text{테스트 한 번에 걸리는 시간}: t(x) = n \times x + m\] \[\text{총 예상 시간}: f(x) = t(x) \times E(X = x) = \frac{n \times x + m}{1 - (1 - p \times 10^{-4})^x}\]

• 위 수식은 미분가능하며, 미분계수가 0인 점은 단 한개만 존재한다. 따라서, 유니모달 함수의 형태를 가지므로 삼분 탐색을 통해서 총 예상 시간의 최솟값을 찾을 수 있다.

💻 코드 구현

#include <bits/stdc++.h>
#define fastio cin.tie(0)->ios::sync_with_stdio(0)

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvll = vector<vector<ll>>;
using vll = vector<ll>;
using vpi = vector<pi>;

ll N, M, P;

long double eval(int num) {
    return (N * num + M) / (1 - pow(1 - P * 1e-4L, num));
}

int main() {
    fastio;

    int t;
    cin >> t;
    while (t--) {
        cin >> N >> M >> P;
        int l = 1, r = 1e6;
        while (r - l > 2) {
            int p1 = l + (r - l) / 3;
            int p2 = r - (r - l) / 3;
            if (eval(p1) < eval(p2)) {
                r = p2;
            } else {
                l = p1;
            }
        }
        long double ans = numeric_limits<long double>::max();
        for (int i = l; i <= r; ++i) {
            ans = min(ans, eval(i));
        }
        cout << fixed << setprecision(10) << ans << "\n";
    }
}

📝 코드 설명

🔧 트러블 슈팅

• 입력 크기가 크므로 타입에 주의한다.

📚 참고자료