[ 백준 ] 13251 / 조약돌 꺼내기

金弘均·2021년 9월 14일
0

Baekjoon Online Judge

목록 보기
13/228
post-thumbnail

# Appreciation

/*
 * Problem :: 13251 / 조약돌 꺼내기
 *
 * Kind :: Math
 *
 * Insight
 * - 처음엔 같은 색 조약돌을 뽑을 수 있는 경우에
 *   전체 조약돌을 뽑을 수 있는 경우의 수를 나눌려고 했으나...
 *   max(N)=50*50=2500 인데
 *   여기서 K 가 1250 이라면
 *   a_C_r 을 n 개 중에서 r 개를 뽑는 경우의 수 nCr 을 구하는 것이라 할 때,
 *   2500_C_1250 을 구해야하는... 대참사가 일어나게 된다
 *   + 여기서 놓친 부분은 확률이라는 것과
 *     오차가 범위내의 정답이면 된다는 것
 *     각 색깔에 대해 뽑는 모든 경우의 수를 구하는 것이 아니라
 *     각 색깔에 대해 뽑을 수 있는 확률들의 합을 구하는 식으로 접근해야 한다
 *     # i=[1,M] 에서 A[i] >= K 이면
 *       i 색깔에 대해 뽑을 수 있는 확률은
 *       A[i]_C_N 인데 이 확률을 구하기 위해서는
 *       초기 확률의 값 prob 을 long double 자료형으로 선언하고 초기값 1 로 설정한 뒤
 *       for (int i=0; i<K; i++) {
 *           prob *= (A[i]-i);
 *           prob /= (N-i)
 *       } 를 통해 구할 수 있다
 *       이러한 각 색깔에 대한 확률을 모두 합하면 답을 구할 수 있다
 *
 * Point
 * - 조합에 관한 문제이지만
 *   정석대로 풀면 오히려 풀지 못하는 문제...
 *   + 확률과 오차에 대해 다시 생각해볼 수 있던 문제였다
 *
 * - 부동소수점 오차가 발생할까봐
 *   애초에 long double 자료형을 사용했다
 *   + double 로도 가능했더라~
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <numeric>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int M; cin >> M;
    int A[M];
    for (int i=0; i<M; i++)
        cin >> A[i];
    int K; cin >> K;

    // Process
    long double ans = 0; /* 뽑은 조약돌이 모두 같은 색일 확률 */
    int N = accumulate(A, A+M, 0); /* 전체 조약돌 개수 */
    for (int i=0; i<M; i++) {
        if (A[i] >= K) {
            long double prob = 1; /* i 색깔 조약돌이 모두 같은 색일 확률 */
            for (int j=0; j<K; j++) {
                prob *= (A[i]-j);
                prob /= (N-j);
            } ans += prob;
        }
    }

    // Control : Output
    printf("%.9Lf\n", ans);
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글