저희도 1부터 N까지의 수 중에 서로 다른 M개의 수를 고를건데, 적어도 K개의 수가 같으면 당첨입니다!”
2. 문제풀이
지민이가 1부터 N까지의 수 중에 서로 다른 M개의 수를 골랐을 때,
복권과 적어도 K개의 수가 같으면 당첨이다.
조합, 확률 관련 문제로 고등학교 문제 푸는 것과 비슷한 느낌을 받았다.풀이 방법은 아래 그림과 같다.
문제의 예제 입력 4에 대한 풀이 예시이다.위 풀이방법을 일반화해보면 다음과 같은 순서로 정의된다.
1.1 ~ N까지의 수 중 M개를 선택할 경우의 수 구하기 (분모)
2.적어도 N개 이상이 같을 확률을 차례로 구하고 더하기 (분자)
3.각 분모와 분자에 해당하는 수를 이용해 확률 계산
이를 코드에 적용해보면 아래와 같다.
3. 소스코드
#include <iostream>
using namespace std;
// 팩토리얼 구하는 함수
int fac(int num) {
if (num <= 1) {
return 1;
}
else {
return num * fac(num - 1);
}
}
int main() {
int N; // 1부터 N까지의 수 중
int M; // 서로 다른 M개의 수를 채택
int K; // 적어도 K개가 같으면 당첨
int denominator; // N개 중 M개를 선택할 경우의 수 (분모)
int numerator; // 적어도 K개가 같을 경우의 수 (분자)
double result;
cin >> N >> M >> K;
denominator = fac(N) / (fac(M) * fac(N - M));
numerator = 0;
for (int i = K; i <= M; i++) {
// 지민이와 복권 숫자가 같은 것에서 뽑을 경우의 수
int jimin = fac(M) / (fac(i) * fac(M - i));
// 지민이와 복권 숫자가 다른 것에서 뽑을 경우의 수
int lotto = fac(N - M) / (fac(M - i) * fac(N - M - M + i));
numerator += jimin * lotto;
}
result = double(numerator) / double(denominator);
cout.precision(10);
cout << result;
return 0;
}
먼저, 확률을 구하기에 앞서, 조합을 이용해 풀었기 때문에
위와 같은 팩토리얼 함수를 재귀를 이용해 구현했다.
메인 함수에서는 N, M을 입력받고, 2. 문제풀이에서 이야기한 분모와 분자에 해당하는 값을 구했다.
여기서, 분자에 해당하는 적어도 N개 이상이 같을 경우의 수는
for문을 이용해 값을 조정해나가며 구해주었다.
마지막 확률을 출력할 때에는 cout.precision(10)을 이용해 10^-9 까지 출력하도록 했다.
