문제설명
접근방식
문제의 아이디어 자체는 매우 간단하다. N개의 동전 A[i]개를 랜덤하게 골라서 뒤집는 작업을 i번 진행하였을 때 최총적인 결과의 기댓값을 구하는 문제이다. 이를 풀이하기 위해서는 '기댓값의 선형성'이라는 개념을 이해하고 있어야 한다. 쉽게 비유를 들어서 설명하자면 도박사의 오류와 유사한 맥락의 확률 개념이다. 이전까지 발생한 사건들과 독립적으로 현재 나의 베팅 사건이 이루어지듯이 동전을 뒤집는 확률 또한 동일하게 각각의 동전 입장에서의 확률은 독립적으로 계산이 되어야 하는 것이다.
문제를 풀이할 때 개별 동전이 뒤집어지는 순서에 따라서 이후에도 또 어떻게 뒤집혀질지 여부를 고려해야 하기 때문에 이를 연속적으로 하나의 시퀀스로 묶어서 처리하려고 접근하게 되면 매우 복잡한 문제풀이가 될 것이다. 하지만 현재 문제에세 구하고자 하는 것은 전체 동전들의 앞면 기댓값이므로 그 시퀀스 전체들의 확률은 결국에는 동일한 확률값을 나눠가지게 되는 것으로 봐도 무리가 없다.
정리하자면 i번째 시퀀스에서 N개 중 a개의 앞면과 N-a개의 뒷면으로 구성된 상황에서 K개를 랜덤으로 뒤집는다고 했을 때 얻게 되는 앞면 기댓값은 다음과 같다
a * (1 - (K/N)) + (N-a) * (K/N) 각각의 동전이 뒤집어질 확률은 모두 동일하게 N개 중에서 K개로 뽑힐 확률인 K/N이고 따라서 앞면은 그대로 유지되게 뽑히질 않을 확률을 곱해주고 뒷면인 동전들은 뽑혀서 뒤집히게 되거 앞면이 나오게 될 확률을 곱해서 두 기댓값을 더해주면 된다.
이를 바탕으로 i번의 절차에 대해서 계속 이전 기댓값에 업데이트를 해주는 방식으로 나아가면 된다.
dp[i] = dp[i-1] * (1- A[i]/N) + (N-dp[i-1])*(A[i]/N)
i번쨰 뒤집기를 시도하고 난 뒤의 앞면 기댓값저런 방식으로 dp를 쌓아가도 되지만 굳이 배열로 각각의 값을 저장할 필요없이 하나의 변수에 업데이트를 해가는 방식으로 구현을 해도 된다.
C++코드
//https://www.acmicpc.net/problem/13255
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair <int, int>;
int main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//freopen("inp.txt", "r", stdin);
int N, K;
cin >> N >> K;
double pr = N;
while(K--){
int a;
cin >> a;
double temp = 0.0;
temp += pr * (1 - (double)a / N);
temp += (N-pr) * ((double) a / N);
pr = temp;
}
cout.fixed;
cout.precision(11);
cout << pr;
}
/*
기댓값의 선형성
: 제비뽑기에서 먼저 뽑든지 나중에 뽑든지가 확률적으로는 영향을 안 미치듯이
전체 N개에서 a개를 랜덤하게 수행한다고 했을 때
각각의 개체가 수행될 확률은 모두 a/N으로 동일함
-> 따라서 한 과정을 거칠때마다 이전 단계에서 가지고 있던 기댓값을 바탕으로
(앞면 기댓값 * 안 뒤집을 확률) + (뒷면 기댓값 * 뒤집을 확률)
이런 방식으로 업데이트해나가면 된다.
*/