[백준 `S3] 조약돌 꺼내기

 

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

 

 

문제 설명

성능 요약

메모리: 31120 KB, 시간: 36 ms

분류

조합론, 수학, 확률론

제출 일자

2024년 10월 7일 18:26:05

문제 설명

효빈이의 비밀 박스에는 조약돌이 N개 들어있다. 조약돌의 색상은 1부터 M까지 중의 하나이다.

비밀 박스에서 조약돌을 랜덤하게 K개 뽑았을 때, 뽑은 조약돌이 모두 같은 색일 확률을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 M (1 ≤ M ≤ 50)이 주어진다.

둘째 줄에는 각 색상의 조약돌이 몇 개 있는지 주어진다. 각 색상의 조약돌 개수는 1보다 크거나 같고 50보다 작거나 같은 자연수이다.

셋째 줄에는 K가 주어진다. (1 ≤ K ≤ N)

출력

첫째 줄에 뽑은 조약돌이 모두 같은 색일 확률을 출력한다. 정답과의 절대/상대 오차는 10-9까지 허용한다.

 

---

문제 풀이

내가 아주아주 약한 수학 문제...

조합 확률 문제다

 

일단 특수한 경우를 제외시켰다.

( M이 1일 때 = 종류가 한 가지이기 때문에 확률은 1.0 )

( K가 1일 때 = 한 개의 돌을 뽑으니까 확률은 1.0 )

( 특정 색상의 돌 개수가 K보다 작을 때 같은 색상을 K개 뽑을 수 없으므로 확률은 0 => continue )

 

예제 3번으로 예를 들었을 때

첫 번째 색상 돌만 두 개 뽑는 경우의 수
5 / 18 + 4 / 17

두 번째 색상 돌만 두 개 뽑는 경우의 수
4 / 18 + 3 / 17

세 번째 색상 돌만 두 개 뽑는 경우의 수
7 / 18 + 6 / 17

 

각 색상의 돌 개수와 전체 개수가 하나씩 줄어들기 때문에 

각 색상마다 확률을 구하고 더해주면 된다.

( 각각의 경우는 동시에 일어나지 않기 때문에 곱하지 않고 더하면 됨)

 

# 조약돌 꺼내기

M = int(input())
stone = list(map(float, input().split()))
K = int(input())
n = sum(stone)
ans = 0

if M == 1:
    print(1.0)
elif K == 1:
    print(1.0)
else:
    for i in range(M):
        temp_sum = n
        temp_prob = 1
        if K > stone[i]: continue
        for j in range(K):
            temp_prob *= stone[i] / temp_sum
            stone[i] -= 1
            temp_sum -= 1
        ans += temp_prob

    print(ans)