백준 BOJ 17030번 : Cow Dating 풀이 (Diamond V, 투 포인터)

백준 BOJ 17030번 : Cow Dating

문제 난이도 : Diamond V

알고리즘 분류 : 투 포인터, 누적 합

 

N개의 선택받을 확률 p_i가 주어질 때 (실제 입력은 p_i의 10^6배를 한 값들로 주어진다.) 연속한 구간 p_l ~ p_r을 선택하여 그들 중 하나에게만 선택이 될 확률의 최댓값을 구하는 문제이다.

 

 

 

구간을 잡고 관계식을 찾는 것이 핵심이다.

구간 [l, r]에서의 확률이 이미 있을 때, 어떤 조건에서 구간을 늘렸을 때 확률이 늘어나는지 계산해보자.

 

구간 [l, r]에서 하나에게만 선택받을 확률 f(l, r)은 위의 식처럼 나타낼 수 있고, 거기에 항을 하나 추가하여 f(l, r+1)을 관계식으로 구할 수 있다.

그러면 f(l, r+1) > f(l, r)일 조건을 찾아주면 된다.

 

식을 풀어보면 p_i / (1 - p_i)의 구간 합이 1보다 작을 때와 동치이므로, [1, 1]에서 시작하여 해당 조건을 만족할 때 오른쪽 구간을 늘리고 그렇지 않으면 왼쪽 구간을 줄이는 식으로 투 포인터 알고리즘을 통해 O(N)에 풀이할 수 있다.

 

이 문제에서는 O(N^2) 풀이를 허용하지 않으므로 (N ≤ 60,000) 누적 합을 이용하여 O(1) 시간에 위의 시그마 식을 구해줄 수 있도록 해야한다.

또한 구간 곱을 사용하면 구간이 넓어질 때 값이 0에 수렴하여 오차가 발생하므로 앞에 곱해지는 곱은 매 반복문마다 갱신해서 구해주는 방식을 사용해주면 된다.

 

 

#include <bits/stdc++.h>
#define int long long
using namespace std;

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

    int N; cin >> N;

    vector<double> v(N+1);

    for(int i=1; i<=N; i++) {
        cin >> v[i];

        v[i] *= 1e-6;
    }

    vector<double> u(N+1);

    for(int i=1; i<=N; i++)
        u[i] = u[i-1] + v[i] / (1 - v[i]);

    int i = 1, j = 1;
    double p = 1 - v[1], ans = 0;

    while(j <= N) {
        ans = max(ans, p * (u[j] - u[i-1]));

        if(u[j] - u[i-1] < 1) {
            j++;
            p *= (1 - v[j]);
        }
        else {
            i++;
            p /= (1 - v[i-1]);
        }
    }

    ans = (int)(ans * 1e6);

    cout << ans << "\n";
}