441 words
2 minutes
[BOJ] 타율 분석
TimeLimit | MemoryLimit | Condition | TAG |
---|---|---|---|
1s | 1024MB | (0.162 ≤ A ≤ 0.412, 1 ≤ B ≤ 300) | Dynamic Programming, Math |
이걸 의도한건진 모르겠지만 그냥 각 상황별 경우의 수를 구해주고 나눠주는 절차를 밟는데 전체 가짓수가 A고 선택하는 수가 n이라고 하면
A!/n!(A - n)!이 되는데 이때 식을 보면 결국 대칭성을 가지고 있음을 바로 알 수 있다. 그래서 그거 이용해서 150까지 팩토리얼 구하고나서 그거 대칭성 이용해서 300까지 얻을 수 있다.
그러고는 그냥 간단한 확률 계산이고 누적해서 더해주면 답을 간단히 구할 수 있다.
정답 코드
#include <iostream>
#include <queue>
#include <set>
#include <algorithm>
#include <random>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#define MOD 1000000007LL
#define MAX 1'000'000LL
using namespace std;
using ll = long long;
double A;
int B;
double fact[301]; // 골랐던 거, 안 골랐던 거
double dp[152];
int main() {
cin >> A >> B;
double y = A;
double n = 1 - A;
double std = 0.05;
fact[0] = 1;
fact[1] = 1;
fact[2] = 2;
fact[3] = 6;
fact[4] = 24;
fact[5] = 120;
for(int i = 6; i < B; i++) fact[i] = fact[i-1] * i; // 어차피 내가 구하려는게 대칭성을 띄고 이ㅣㅆ음.
dp[0] = 1;
for(int i = 1; i < B / 2 + 2; i++) dp[i] = (dp[i-1] * (B - i + 1)) / i;
// cout << dp[149] << " " << dp[151] << "\n";
double result = 0;
for(int i = 0; i <= B; i++){
double ok = pow(y, i);
double no = pow(n, B - i);
// cout << ok <<" " << no <<" " << ok * no <<"\n";
double c;
if(i > B / 2) c = dp[B * 2 - i] * ok * no;
else c = (dp[i] * ok * no);
// cout << i << " " << dp[i] << " " << c <<"\n\n";
result += c;
if(result >= std) {
cout << i << "\n";
break;
}
}
return 0;
}