https://www.acmicpc.net/problem/25257
25257번: Monty's Hall
You have explored the deep catacombs under a long lost city for the past couple of hours and finally you have reached their end: The hall of the undead wizard Monty. His restless spirit materialises in front of you and you prepare for battle. However, it t
www.acmicpc.net
몬티 홀 문제는 상당히 유명하므로, 바꾸는게 무조건 이득이다 정도는 다들 알고 있을 것이다.
이 문제는 몬티 홀 문제를 일반화한 것으로, 전체 문 D개가 있고 문 하나에 보물이 있을 때, S개의 문을 처음에 고르면, 나머지 D-S개의 문 중 E개를 열어 보물이 없음을 알려 준다. 이 때 고르는 문을 바꾸어 얻을 수 있는 최대 확률을 물어본다.
문제 상황을 순서대로 생각해 보자.
먼저 S개를 고르면, 고른 문 각각에 보물이 있을 확률은 1/D이고, 고르지 않은 문 중 보물이 있을 확률은 D-S/D이다.
여기서, E개의 문을 열면 D-S-E개의 문에 이 확률이 나눠지게 되고, (고르지 않은 문 중에 보물이 있을 확률이 D-S/D임이 유지되어야 하기 때문) 고르지 않은 문 중 열리지 않은 문 D-S-E개에 보물이 있을 확률은 각각 D-S/D(D-S-E)이다.
마지막으로 S<=D-S-E 이면 D-S-E 개중 S개를 고르면 되므로 답은 S(D-S)/D(D-S-E),
S>D-S-E일 경우 D-S-E개의 문을 모두 고르고 확률이 1/D인 문 2S+E-D개를 고르면 D-S/D + (2S+E-D)/D = S+E/D 가 답이다.
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 11873 최대 직사각형 (1) | 2023.02.04 |
|---|---|
| 백준 1733 등번호 (0) | 2023.02.03 |
| 백준 14458 소가 길을 건너간 이유 10 (2) | 2023.02.01 |
| 백준 6101 식당 (0) | 2023.01.31 |
| 백준 3321 가장 큰 직사각형 (1) | 2023.01.30 |
