반응형
문제출처 : https://www.acmicpc.net/problem/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;
}
반응형
'알고리즘 > 백준' 카테고리의 다른 글
백준1388-바닥장식(브론즈1) (0) | 2020.09.09 |
---|---|
백준1384-메시지(브론즈1) (0) | 2020.09.08 |
백준1357번-뒤집힌덧셈(브론즈1) (0) | 2020.09.04 |
백준1236-유진수(브론즈1) (0) | 2020.09.03 |
백준1268 - 임시반장정하기(브론즈1) (0) | 2020.09.02 |