백준 13251 조약돌 꺼내기

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

13251번: 조약돌 꺼내기

 

[주의할 조건]

색상의 종류: M개 (1~50)

조약돌 총 갯수: N개 (1~50*50)....각 색상의 조약돌 개수는 1<=x<=50 이므로 

뽑는 돌 갯수: K개 (1~50*50)

출력값의 오차는 10^-9까지 허용....소수점 이하 10자리까지 구하면 오차 내의 범위로 구해진다.

깔끔하게 %.15lf로 구하면 됨!

 

[구하는 값]

뽑은 조약돌이 모두 같은 색일 확률

 

[생각의 흐름]

1. 처음에는  분자: 전체 조약돌에서 뽑는 경우의 수 , 분모: a컬러로 모두 뽑는 수+ b컬러로 뽑는 수....

로 둬서 분모/분자 = (aCk + bCk + cCk ...) /(nCk) 를 계산하려고 했다. <-a: 색상이 a인 돌의 갯수

 

하지만!!그렇게하면 DP로 풀어도 계속 오답이 뜬다..

조합

이 문제를 풀어보면 알겠지만, 

100C50 = 100891344545564193334812497256

정도되는 아주아주 큰 수이면 long long의 범위조차 벗어나기 때문에 

string을 사용해서 big integer를 구현해야한다. 한마디로 십진수 덧셈을 구현해야 한다는 말...ㅎㅎ

조약돌 구하기 문제에선 2500C50도 구할 수 있어야하기 때문에

처음 생각한 방법으로 풀면 오답이 나올 수 밖에 없다. 그렇다고 이 문제에서 big integer를 구현하기엔...

너무 귀찮다ㅠㅠ

 

2.그래서 아예 확률을 구하는 식 자체를 다르게 잡아야한다. (이 문제 분류가 '큰 수'가 아닌 '확률'인 이유다.)

경우의 수를 다 구해서 확률을 계산하지 말고, 큰 수가 나오기 전에 미리미리 확률로 만들어두면 된다.

즉,  "각 컬러에 대해 뽑는 모든 경우의 수/ 모든 경우의 수"를 계산하는 것이 아니라

"a컬러에 대해 뽑는 확률"+"b컬러에 대해 뽑는 확률" + ....을 구해야하는 것이다.

 

 

n=200 , m= 50, k=3 에서 a컬러의 돌갯수가 40이라고 가장하자. 

 

a컬러로만 모든 돌을 뽑는 확률

= (40/200)*(39/199)*(38/198)= (40*39*38)/ (200*199*198).

 

처음부터 조합식으로 바로 풀려고 하면 쉽게 오답이 뜰 수 있는 문제이다. 

이런 식으로 각 컬러별로 확률을 구해서 모두 더해준 뒤, 소수점 이하 15자리까지 출력을 하면 통과할 수 있다. 

 

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
int color[50];
double p[50];
int main() {  
	int n = 0, m, k;
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		scanf("%d",&color[i]);
		n += color[i];
	}
	scanf("%d",&k);

	for (int i = 0; i < m; i++) {
		if (color[i] < k)  //!!!!이 경우는 넘어가야함. 2개중에서 4개 못고르니..
			continue;
		double tmp = 1.0;
		for (int j = 0; j < k; j++) {  //k를 빼서 0이되는 경우 있을수도 있으니까..
			tmp *= (double)(color[i] - j) / (n - j);
		}
		p[i] = tmp;
	}
	double ans = 0;
	for (int i = 0; i <m; i++) {
		ans += p[i];
	}

	printf("%.15lf",ans);  
	return 0;
}