문제
N개의 숫자 중 M개를 선택할 때, 당첨 번호와 K개 이상 일치할 확률을 구하라.
입력
첫째 줄에 N, M, K가 주어진다.
출력
K개 이상 일치할 확률을 출력한다.
예제
| 입력 | 출력 |
|---|---|
5 3 2 | 0.3 |
풀이
조합론으로 일치 개수별 경우의 수를 계산하여 확률을 구한다.
- 일치 개수 i = K부터 M까지 반복한다
- 당첨 번호 M개 중 i개를 선택하는 경우: C(M, i)
- 나머지 N-M개 중 M-i개를 선택하는 경우: C(N-M, M-i)
- 전체 경우의 수 C(N, M)으로 나누어 확률을 구한다
핵심 아이디어: 초기하분포를 이용하여, 당첨 번호에서 i개 + 비당첨에서 M-i개를 뽑는 조합으로 계산한다.
코드
const solution = (input) => {
const [N, M, K] = input[0].split(" ").map(Number);
const factorial = (n) => { if (n === 0) return 1; return n * factorial(n - 1); };
const comb = (n, m) => { if (n < m) return 0; return factorial(n) / (factorial(m) * factorial(n - m)); };
let tmp = 0;
for (let i = K; i <= M; i++) { tmp += comb(M, i) * comb(N - M, M - i); }
return tmp / comb(N, M);
};
const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
console.log(solution(input));복잡도
- 시간: O(M)
- 공간: O(1)