[BOJ] 조약돌 꺼내기

문제

효빈이의 비밀 박스에는 조약돌을 N개 들어있다. 조약돌의 색상은 1부터 M까지 중의 하나이다.

비밀 박스에서 조약돌을 랜덤하게 K개 뽑았을 때, 뽑은 조약돌이 모두 같은 색일 확률을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 M (1 ≤ M ≤ 50)이 주어진다.

둘째 줄에는 각 색상의 조약돌이 몇 개 있는지 주어진다. 각 색상의 조약돌 개수는 1보다 크거나 같고 50보다 작거나 같은 자연수이다.

셋째 줄에는 K가 주어진다. (1 ≤ K ≤ N)

출력

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

 

13251

맞았습니다!!

50852

20

C++14 / 수정

957

2분 전

 

1) 조합을 사용한다. 같은 색상 color[i] C k를 계산한 값들을 모두 더한 후에 조약돌의 전체 개수(total) C k를 나눈 값이 정답 

2) 보통 조합을 구할 때 재귀를 많이 사용하는 편인데 시간초과가 발생할 수 있기 때문에 (조약돌의 최대 개수 50개 * 뽑을 조약돌의 최대 개수 50 하면 2500! 이다.) DP를 사용해서 값을 미리 저장해두었다. 

 

#include <iostream>
#include <vector>
#define MAXX 2501
using namespace std;
 
double combination[MAXX][MAXX];
int m, k, total = 0;
 
void comb()
{
    combination[0][0] = combination[1][0] = combination[1][1] = 1;
 
    for (int i = 2; i <= total; i++)
    {
        combination[i][0] = combination[i][i] = 1;
        for (int j = 1; j <= i; j++)
        {
            combination[i][j] = combination[i - 1][j - 1] + combination[i - 1][j];
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int color[51] = {0};
 
    cin >> m;
 
    for (int i = 0; i < m; i++)
    {
        cin >> color[i]; //색상에 마다 조약돌의 개수
        total += color[i];
    }
 
    cin >> k; //몇 개 뽑을 지
 
    comb();
    double tmp = 0, all = combination[total][k];
    for (int i = 0; i < m; i++)
    {
        tmp += combination[color[i]][k];
    }
 
    double res = tmp / all;
 
    printf("%.18lf", res);
 
    return 0;
}