Baekjoon 13251 조약돌 꺼내기

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

소스결과 50856KB / 24 ms

출처 Baekjoon

언어 C++ 14

분류 확률

 

설명

m개의 색으로 이루어진 조약돌 중 k개를 뽑았을 때 모두 같은 색의 조약돌을 뽑을 확률을 구하여라.

 

처음 접근했을 때는 모듈러를 이용하여 큰 수를 처리하는 방법을 선택 했었다.

페르마의 소정리를 통해 모듈러의 나눗셈에 대한 역원 처리를 통해 곱셈으로 변환하는 방법이었는데

모듈러가 적용되면 확률이 1을 넘어가는 상황도 나온걸 보아하니 잘못된 방법이었나보다.

 

문제 해결에 사용한 방법은 설마 될까 했던 방법인데 double을 이용하여 직접 모든 경우를 다 구하는 것이다.

double의 최대 범위가 10^308까지이기때문에 가능하다.

자료형을 double이 아닌 long double로 선언하면 오답으로 나오지만 double로 실행하면 정답이 된다.

 

조합의 경우의 수를 해결 하는 알고리즘으로는 파스칼의 삼각형을 사용한다.

 

알고리즘

1. 각 색마다 돌을 입력받는다. 동시에 모든 돌의 개수를 저장한다.

2. 각 돌에 대해서 n C k를 구한다.

3. 구해진 모든 n C k를 더한다. (1)

4. 모든 돌에 대해서 tn C k를 구한다. (2)

5. (1) / (2)를 소수 18자리까지 출력한다.

 

소스코드

#include <iostream>
#include <vector>

using namespace std;

const short MAX = 2500;
const short R_MAX = 50;

typedef double ld;

ld triangle[MAX + 1][MAX + 1];

void initPascal() {
	triangle[0][0] = triangle[1][0] = triangle[1][1] = 1;
	for (int i = 2; i <= MAX; ++i) {
		triangle[i][0] = triangle[i][i] = 1;
		for (int j = 1; j <= i; ++j) {
			triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
		}
	}
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	initPascal();

	int m; cin >> m;
	int total = 0;
	vector<int> vec(m);

	for (int i = 0; i < m; i++) {
		cin >> vec[i];
		total += vec[i];
	}

	int k; cin >> k;

	ld base = triangle[total][k];
	ld sumStone = 0;

	for (int i = 0; i < m; i++) {
		sumStone += triangle[vec[i]][k];
	}

	printf("%.18lf", sumStone / base);

	return 0;
}