[백준 13251번] 조약돌 꺼내기 (C++)

문제링크 : https://www.acmicpc.net/problem/13251

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

const int MOD = 1000000007;

int arr[51];

int main() {
    
    int M, K;
    int sum = 0;
    cin >> M;
    for(int i=0; i<M; i++) 
    {
        cin >> arr[i];
        sum += arr[i];
    }
    cin >> K;

    double result = 0;
    for(int i=0; i<M; i++)
    {
        if(arr[i] < K) continue; //불가
        double tmp = 1.0;
        for(int j=0; j<K; j++)
        {
            tmp *= double(arr[i]-j)/double(sum-j);
        }
        result += tmp;
    }

    cout << fixed << setprecision(9) << result;
    return 0;
}

 

먼저 뽑은 조약돌이 모두 같은 색일 확률을 구하기에, 입력받은 조약돌의 모든 개수를 구해준다.

그리고 기본적으로 조약돌의 개수가 K보다 작다면 아에 불가능한 케이스이기에 스킵한다.

 

기본적으로는 arr[i]/sum이 기본적인 확률이다. (전체 조약돌 중 현재 해당 색깔 확률)

여기서 K개에 따라 1개를 고르고 또 나머지에 대한 확률을 생각하면 (arr[i]-1)/(sum-1)일 것이다.

이게 K개 만큼 반복되므로 결과적으론 (arr[i]-j)/(sum-j)이 공식이 된다.

이때 계산은 double로 하여 정확도를 높이고, 문제 조건에 따라 절대/상대 오차는 10^(-9)까지 인점을 참고하여야 한다.