# [Silver IV] 복권 #### [문제 링크](https://www.acmicpc.net/problem/1359) ## 문제 설명 <p>어제, 지민이는 몰래 리조트에 갔다가 입구에 걸려있는 복권 광고를 하나 보았다.</p> <p>“1부터 N까지의 수 중에 서로 다른 M개의 수를 골라보세요. 저희도 1부터 N까지의 수 중에 서로 다른 M개의 수를 고를건데, 적어도 K개의 수가 같으면 당첨입니다.!”</p> <p>지민이는 돌아오면서 자신이 복권에 당첨될 확률이 궁금해졌다.</p> <p>지민이가 복권에 당첨될 확률을 구하는 프로그램을 작성하시오.</p> ## 입력 <p>첫째 줄에 세 정수 N, M, K가 주어진다.</p> ## 출력 <p>첫째 줄에 지민이가 복권에 당첨될 확률을 출력한다. 절대/상대 오차는 10^-9까지 허용한다.</p> ## 풀이 #### 이 문제에서 N의 최댓값이 8이기에 가장 많은 연산이 필요한 경우도 ₈C₄ * ₈C₄ = 4900회이고, 브루트포스로도 충분히 시간 안에 돕니다. #### 그래서 하나하나 가능한 경우의 수를 구해 풀어도 되었지만 수식을 써서 계산을 해 풀고 싶었기에 조합을 사용해 풀었습니다. #### 전체 경우의 수는 n개의 카드 뭉치에서 순서 상관없이 m개를 뽑는 것이기에 _nC_m 입니다. #### 그리고 내가 뽑은 카드 중에서 k개 이상 똑같은 경우의 수는 #### 1. 내가 뽑은 카드에서 k개를 선택하고, 내가 뽑지 않은 카드에서 m-k개를 선택하는 경우 #### 2. 내가 뽑은 카드에서 k+1개를 선택하고, 내가 뽑지 않은 카드에서 m-k-1개를 선택하는 경우 #### 3. 내가 뽑은 카드에서 k+2개를 선택하고, 내가 뽑지 않은 카드에서 m-k-2개를 선택하는 경우 #### ... #### m-k+1. 내가 뽑은 카드에서 m개를 선택하고, 내가 뽑지 않은 카드에서 0개를 선택하는 경우 #### 이 전체를 더한 값인 _mC_k * _n-mC_m-k + _mC_k+1 * _n-mC_m-k-1 + ... + _mC_m * _n-mC₀ 입니다. #### 이제 이 값을 전체 경우의 수인 _nC_m로 나누면 정답이 나옵니다. ``` c++ #include<bits/stdc++.h> using namespace std; int combination(int n, int r) { int res=1; for(int i=n;i>n-r;i--) { res *= i; } for(int i=1;i<=r;i++) { res /= i; } return res; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n, m, k; cin >> n >> m >> k; int total=0; for(int i=k;i<=m;i++) { total += combination(m, i)*combination(n-m, m-i); } cout << setprecision(9) << fixed << total / (long double)combination(n, m); } ```