문제

어제, 지민이는 몰래 리조트에 갔다가 입구에 걸려있는 복권 광고를 하나 보았다.

“1부터 N까지의 수 중에 서로 다른 M개의 수를 골라보세요. 저희도 1부터 N까지의 수 중에 서로 다른 M개의 수를 고를건데, 적어도 K개의 수가 같으면 당첨입니다.!”

지민이는 돌아오면서 자신이 복권에 당첨될 확률이 궁금해졌다.

지민이가 복권에 당첨될 확률을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 정수 N, M, K가 주어진다.
2 ≤ N ≤ 8
1 ≤ M ≤ N-1
1 ≤ K ≤ M

출력

첫째 줄에 지민이가 복권에 당첨될 확률을 출력한다. 절대/상대 오차는 10^-9까지 허용한다.

예제 입력

3 1 1

예제 출력

0.3333333333333333

내가 했던 풀이

적어도 K개의 수가 같으면 당첨이기 때문에, M개 중에 K개가 맞을 확률이 아닌 K~M개가 맞을 확률을 구해주어야 한다.
possibility는 N개 중에 M개를 선택할 확률에서 M개 중에 K개를 선택할 확률과 전체에서 M개를 제외한 수 중에 M-K개를 선택할 확률을 구해주어야 한다. 왜나하면, 만약 3개 중에 2개가 맞을 확률일 경우, 3개 중에 2개가 맞고, 1개가 틀릴 확률도 고려해야 하기 때문이다. 이런 식으로 K부터 M까지 맞을 확률을 모두 더해준 값이 정답이다.

코드

const fs = require('fs');
let input = fs.readFileSync(0, 'utf-8').toString().trim().split(' ');

let N = Number(input[0]);
let M = Number(input[1]);
let K = Number(input[2]);

function factorial(n) {
  if (n === 0 || n === 1) return 1;
  let result = 1;
  for (let i = 2; i <= n; i++) {
    result *= i;
  }
  return result;
}

function combination(n, r) {
  if (n < r) return 0;
  return factorial(n) / (factorial(r) * factorial(n - r));
}

function possibility(n, m, k) {
  return (combination(m, k) * combination(n - m, m - k)) / combination(n, m);
}

let cases = 0;
for (let k = K; k <= M; k++) {
  cases += possibility(N, M, k);
}
console.log(cases);

회고

적어도 K개가 맞을 확률이라 K, K+1...까지는 생각해냈는데 K개를 선택하고 나머지는 틀릴 확률을 구해줘야 한다는 걸 생각하지 못해서 엄청엄청 삽질한 문제............ 확률과 통계를 과감하게 때렸쳤던 전적이 있어서 그런지 조합 부분을 심각하게 못하는 것 같다. 이 부분을 좀 복습을 많이해서 익숙해져봐야 할 것 같다.