13251 조약돌 꺼내기 (조합론, 확률론) [Silver III]

13251번: 조약돌 꺼내기 (acmicpc.net)

 

 

M개의 색, M개의 색을 가진 조약돌이 몇개인지, 랜덤하게 뽑을 수 K를 입력받습니다.

이때 K개의 조약돌이 모두 같은 색일 확률을 구하면 됩니다.

 

2개의 랜덤한 조약돌을 뽑을때의 경우의 수는 이렇습니다. 

총 18개 중 5개의 조약돌이 있는 색을 2번 뽑을 확률 -> 5 / 18 * 4 / 17

 

즉

A개의 조약돌을 가진 색을 2번 뽑을 확률 -> (A개 / 조약돌 총갯수) *  (A - 1개 / 조약돌 총갯수 - 1)

이러한 점화식을 바탕으로 코드를 만들면 쉽게 풀 수 있습니다.

 

 

정답 코드

#include <iostream>
#include <vector>

using namespace std;

static int D[1001]; 
double Total = 0;
int M, K;

// 색상 A 수 / 전체 수 -> 색상 A수 --; (연속 수 <= A 수) -> 반복

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> M;


	for (int i = 0; i < M; i++) {
		cin >> D[i];
		Total += D[i];
	}

	cin >> K;

	double result = 0.0f;
	for (int i = 0; i < M; i++) {

		if (D[i] < K)
			continue;

		double val = 1.0; 

		for (int j = 0; j < K; j++) {
			val *= double(D[i] - j) / (Total - j);
		} 
		 
		result += val;

	}
	 
	cout << fixed; 
	cout.precision(18);
	cout << result;
}