문제 링크 : https://www.acmicpc.net/problem/13258
1. 접근 방법
간단한 확률 계산 문제로, 기댓값을 알아내면 된다
2. 풀이 코드
🖥python 코드 링크 : https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/13000/13200/13258.py
📕코드 해설
우선 각 확률이 어떻게 계산되는지 보면 다음과 같다.
파란색은 당첨된 경우, 빨간색은 당첨되지 않은 경우이다. 그리고 각 경우 확률은 화살표 옆에 같이 표시하였다.
우선 첫 번째 100, 100씩 가지고 있는 경우, 확률은 1/2가 된다.
두 번째는 강호가 200 가지고 있으면 상대방은 100, 100을 가지고 있으면 상대방은 200을 가지게 되고, 당첨 확률은 각각 2/3, 1/3이 된다.
위의 두 과정을 계산하여 최종 금액과 확률은 가장 밑에서 표시한 것처럼 되고, 각 금액과 확률을 곱하여 합하면 200이 나온다.
그런데 이러한 방식으로 진행한다면 최대 50명에 대한 1000번 연산은 거의 불가능할 것이다. 이를 해결하기 위해 각 단계별로 기댓값을 계산하면 다음과 같이 해결할 수 있다.
다음과 같이 각 주마다 기댓값을 저장하는 방식으로 계산할 수 있다. 이 때 계산은 다음과 같이 할 수 있다.
우선, 전체 사람들의 금액과 당첨금은 일정하므로, 나의 금액을 전체 금액으로 나누면 내가 당첨될 확률을 각 주별로 계산할 수 있고, 1에서 확률을 빼면 당첨되지 않을 확률도 구할 수 있다.
이 각각 당첨될 금액, 당첨되지 않을 금액에 지금 금액 + 당첨금, 지금 금액을 곱한 뒤 더하면 기댓값을 구할 수 있다.
def calc_next(now: float, win_prob: float, prize: int) -> float:
win_money = now + prize
return win_money * win_prob + now * (1 - win_prob)
코드로 구현하면 다음과 같다.
지금 금액 now, 당첨금을 합친 금액 win_money를 계산하고 당첨 확률, 당첨되지 않을 확률을 각각 곱해준다.
이 과정을 모든 사람에게, C번 반복하여 해결할 수 있다.
3. 생각 정리
확률 계산 문제는 때로는 매우 간단한데, 가끔 잘 해결되지 않을때도 많은 것 같다.
하지만 기본적인 계산 방식은 유사하여 몇 번만 잘 공부하여 이해한다면 충분히 수월하게 해결할 수 있는 것 같다.
'CS > 알고리즘 & 문제풀이' 카테고리의 다른 글
[Python] 백준 1948 임계경로 (0) | 2022.08.22 |
---|---|
[알고리즘] Segment Tree, lazy propagation (0) | 2022.08.19 |
[Python] 백준 1655 가운데를 말해요 (0) | 2022.08.03 |
[Python] 백준 20149 선분교차 3 (0) | 2022.07.25 |
[Python] 백준 5527 일루미네이션 (0) | 2022.07.11 |
댓글