본문 바로가기

Algorithm/Math

(C++) - 백준(BOJ) 13251번 : 조약돌 꺼내기

반응형

https://www.acmicpc.net/problem/13251

 

13251번: 조약돌 꺼내기

첫째 줄에 뽑은 조약돌이 모두 같은 색일 확률을 출력한다. 정답과의 절대/상대 오차는 10-9까지 허용한다.

www.acmicpc.net

 

확률 문제였습니다.

 

풀이방법

 m개의 색으로 이뤄진 조약돌들 중 k만큼 랜덤으로 골랐을 때 모두 같은 색일 확률을 구해야합니다.

 3개의 색으로 이워진 조약돌들이 각 색마다 3, 5, 7개 있다면 n은 3 + 5 + 7인 15입니다.

 

 k가 지금 뽑아야하는 색의 조약돌의 개수이하라면 뽑을 수 있습니다. k를 3이라고 가정해보면 확률을 구하는 공식은 다음과 같습니다.

정답 : 3/15 * 2/14 * 1/14 + 5/15 * 4/14 *...* 1/11 + 7/15 * ... * 1 / 9

 

상대오차를 고려해 16자리까지 출력합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
double m, k, stonePerColor[51], pro[51], totalStone, ans;
int main(){
    cin >> m;
    for(int i = 0; i < m; i++) cin >> stonePerColor[i], totalStone += stonePerColor[i];
    cin >> k;
    int cnt = 0;

    for(int i = 0; i < m; i++){
        if(stonePerColor[i] < k) continue;
        double tmp = 1.0;
        for(int j = 0; j < k; j++) tmp *= (stonePerColor[i] - j) / (totalStone - j);
        pro[i] = tmp;
    }

    for(int i = 0; i < m; i++) ans += pro[i];
    printf("%.16f",ans);
}