[BOJ/13251/C++] 조약돌 꺼내기

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

문제

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

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

조건

첫째 줄에 M (1 ≤ M ≤ 50)이 주어진다.
둘째 줄에는 각 색상의 조약돌이 몇 개 있는지 주어진다. 각 색상의 조약돌 개수는 1보다 크거나 같고 50보다 작거나 같은 자연수이다.
셋째 줄에는 K가 주어진다. (1 ≤ K ≤ N)

풀이

조합처럼 생겼지만, 확률로 접근하는게 훨씬 편한 문제입니다. 사실 직관적으로 접근을 하면 헤맬일이 없는 문제였던 것 같습니다. 조합으로 접근을 하는 순간 꽤 괴로운 문제입니다.
예를들어

50
50 50 50 50 50 50 50 50 50 50 50 50...
49

라고 입력이 주어진다면, 첫번째 돌 (편의상 1돌 ) 두번째 돌 (2돌)...3돌,4돌 ,..... 50번째 돌까지 각각 같은 색으로 뽑는 경우의 수는 50C49+50C49+...../2500C49가 됩니다. 따라서, 50C49와 같이 "경우의 수"만으로도 풀 수 있는 문제입니다.
2500C49가 약 32309436163815773331032020376000743886903311504689592803009168783407837773566563835216908572832379810000 이기 때문에, 큰 숫자 처리를 위한 문자열 처리로 해야합니다. 불가능한건 아니지만, 문자열로 사칙연산을 하는것은 꽤 고통스러운 과정입니다.

그러므로, 직관적으로 하나씩 하나씩 뽑는 형식으로 구현하면 훨씬 작은 숫자로 전체 확률을 구할 수 있기 때문에, 위와 같은 접근은 괴롭습니다. 틀린 접근은 아닙니다.

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)

using namespace std;

double percentage = 0;

int stone[51];
int M, K;
int total = 0;
int main()
{
  fastio;
  cin >> M;
  for (int i = 0; i < M; i++)
  {
    cin >> stone[i];
    total += stone[i];
  }
  cin >> K;
  // K개를 뽑는 경우
  for (int i = 0; i < M; i++)
  {
    double tmp = 1.0;
    for (int j = 0; j < K; j++)
    {
      tmp *= (double)(stone[i] - j) / (total - j);
      // cout << tmp << '\n';
    }
    percentage += tmp;
  }
  cout << fixed;
  cout.precision(15);
  cout << percentage;

  return 0;
}