백준1359-복권(브론즈1)

문제출처 : https://www.acmicpc.net/problem/1359

1359번: 복권

문제풀이) 조합을 이용하는 문제이다.

먼저 n개 중에서 m개를 선택하는 모든 경우의 갯수를 구한다.

m개중에 k개 이상의 수가 포함되면 당첨

따라서 m개 중에서 k개를 포함하는 경우

m개중에서 k+1개를 포함하는 경우

...

m개중에서 m 개를 포함하는 경우 의 수를 모두 더해 주면 된다.

k개를 포함하는 경우의 수를 구하는 확률을 구해 보면 다음과 같다.

combination(m,k) * combination(n-m,m-k) / combination(n,m)

m개중에서 k개 선택 * 나머지 갯수중에서 k를 제외한 수 / 전체 경우의 수

주의 할점은 n-m 이 m-k 보다 작은 경우가 존재하는데 이때는 예외처리 해 주어야 함

#include <iostream>
#include <cstdio>

using namespace std;

long long Combination(int n,int r)
{
    int p =1;
    int c=1;
    while(r>0)
    {
        c*=n--;
        p*=r--;
    }
    return c/p;
}

int main()
{
    int n,m,k;

    cin >> n >> m >> k;

    double res = 0.0;
    double p = Combination(n,m);
    while(m>=k)
    {
        if(n-m < m-k)
        {
            k++;
            continue;
        }

        double c = Combination(m,k) * Combination(n-m,m-k);

        res += c/p;
        k++;

    }
    printf("%.16f",res);
    return 0;
}