Compy's Blog
441 words
2 minutes
[BOJ] 타율 분석
2025-06-18

타율 분석

TimeLimitMemoryLimitConditionTAG
1s1024MB(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;
}
[BOJ] 타율 분석
https://compy07.github.io/Blog/posts/boj/34029/
Author
뒹굴뒹굴 이정훈 공부방
Published at
2025-06-18