백준 - 1359번 복권 python 문제풀이 [Hellfer]

https://www.acmicpc.net/problem/1359

1359번: 복권

🔷 알고리즘 분류 - 수학, 브루트포스 알고리즘, 조합론 확률론

난이도 - 실버 4

🔶문제 풀이 - 확률론을 이용한 풀이

import math

def combination(n, r): # 조합을 계산하는 함수
    if n < r: # nCr에서 r이 n보다 크면 조합은 0
        return 0
    return math.factorial(n) / (math.factorial(r) * math.factorial(n-r)) # nCr = n! / (r!(n-r)!)

n, m, k = map(int, input().split()) # n, m, k 입력 받기
x = combination(n, m) # 전체 경우의 수 계산
result = 0 # 성공적인 경우의 수를 저장할 변수 초기화

for i in range(k, m+1): # k부터 m까지 반복
    result += combination(m, i) * combination(n-m, m-i) # 성공적인 경우의 수 계산

print(result / x) # 확률 출력 (성공적인 경우의 수 / 전체 경우의 수)

🔶문제 이해하기

n=8은 복권 번호가 총 8개임을 의미하고, m=4는 우리가 선택할 복권 번호가 4개라는 뜻입니다. 

 

k=2는 우리가 당첨될 수 있는 최소 당첨 번호가 2개라는 의미입니다.

우리의 목표는 당첨 번호를 k개 이상 맞추는 경우의 확률을 계산하는 것입니다.

for 루프는 k부터 m까지 반복하므로, 2부터 4까지 반복합니다.

루프의 각 단계에서, 우리는 성공적인 경우의 수를 계산합니다.

1. i=2일 때, 복권 번호 4개 중에서 2개의 당첨 번호를 맞추는 경우의 수는 combination(4, 2)입니다. 

 

나머지 2개의 복권 번호는 당첨 번호가 아니므로, 이는 4개의 남은 복권 번호 중에서 2개를 선택하는 경우의 수로 계산할 수 있습니다. 

 

이는 combination(8-4, 4-2) = combination(4, 2)입니다. 

 

따라서, i=2일 때의 성공적인 경우의 수는 combination(4, 2) * combination(4, 2)입니다.

2. i=3일 때, 복권 번호 4개 중에서 3개의 당첨 번호를 맞추는 경우의 수는 combination(4, 3)입니다. 

 

나머지 1개의 복권 번호는 당첨 번호가 아니므로, 이는 4개의 남은 복권 번호 중에서 1개를 선택하는 경우의 수로 계산할 수 있습니다. 

 

이는 combination(8-4, 4-3) = combination(4, 1)입니다. 

 

따라서, i=3일 때의 성공적인 경우의 수는 combination(4, 3) * combination(4, 1)입니다.

3. i=4일 때, 복권 번호 4개 중에서 4개의 당첨 번호를 맞추는 경우의 수는 combination(4, 4)입니다. 

 

나머지 0개의 복권 번호는 당첨 번호가 아니므로, 이는 4개의 남은 복권 번호 중에서 0개를 선택하는 경우의 수로 계산할 수 있습니다. 

 

이는 combination(8-4, 4-4) = combination(4, 0)입니다. 

 

따라서, i=4일 때의 성공적인 경우의 수는 combination(4, 4) * combination(4, 0)입니다.

이렇게 각 단계에서 성공적인 경우의 수를 모두 더하면 전체 성공적인 경우의 수를 얻을 수 있습니다. 

 

이를 전체 경우의 수 combination(8, 4)로 나누어주면 확률을 얻을 수 있습니다.