문제
풀이
위 문제에서 가장 중요한 점은 적어도 K개의 수가 같으면 당첨이라는 점이다.
M개의 숫자가 완전히 똑같을 때가 아닌 K개 이상 M개 이하의 개수만 맞혀도 된다는 것이다.
그렇다면 이 확률은 전체 경우의 수, 1부터 N까지의 수 중 서로 다른 M개의 수를 고르는 경우의 수 > nCm
지민이가 복권에 당첨될 경우의 수 중 k개가 같을 때 하나만을 예시로 들자면, (지민이가 뽑은 m개의 숫자 중 리조트가 뽑은 숫자 중 일부인 k개를 뽑는 경우의 수) (지민이가 뽑지 않은 N-M개의 숫자 중 회사가 뽑은 M개의 숫자 중 지민이와 같지 않은 M-K개가 있는 경우의 수) > mCk n-mCm-k
하지만 이때 적어도 K개의 수가 같을 때이므로 K개가 같은 경우의 수, K+1개가 같으 경우의 수, K+2개가 같은 경우의 수, ... M개가 같은 경우의 수를 모조리 더해준 후 해당 경우의 수를 전체 경우의 수로 나누어주면 된다.
코드로 표현할 경우 아래와 같다.
def fact(n): #팩토리얼 반환 함수
result = 1
for i in range(1,n+1):
result *= i
return result
def comb(n, m): #조합 반환 함수
if n < m:
return 0
if m == 0 or (n==1 and m==1):
return 1
return (fact(n) // (fact(n-m) * fact(m)))
def probablity(N,M,K): #확률 구하는 경우의 수
total = comb(N, M) # N개의 숫자 중 M개를 뽑는 경우의 수
same = comb(M,K) * comb(N-M, M-K) # 뽑은 M개의 경우의 수 중 K개를 뽑는 경우의 수 * 뽑지 않은 N-M개의 숫자 중 M-K
return same / total
N, M, K = map(int, input().split())
result = 0
for k in range(K, M+1): #K개가 같은 경우부터 M개가 같은 경우 모조리 더하기
result += probablity(N, M, k)
print(result)
