[Python] 백준 13258 복권 + 은행

문제 링크 : https://www.acmicpc.net/problem/13258

13258번: 복권 + 은행

 

1. 접근 방법

간단한 확률 계산 문제로, 기댓값을 알아내면 된다

---

2. 풀이 코드

🖥python 코드 링크 : https://github.com/mintropy/PS/tree/master/BAEKJOON/Python/13000/13200/13258.py

GitHub - mintropy/PS: 다양한 알고리즘 문제 풀이 저장소입니다.

📕코드 해설

우선 각 확률이 어떻게 계산되는지 보면 다음과 같다.

파란색은 당첨된 경우, 빨간색은 당첨되지 않은 경우이다. 그리고 각 경우 확률은 화살표 옆에 같이 표시하였다.

우선 첫 번째 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. 생각 정리

확률 계산 문제는 때로는 매우 간단한데, 가끔 잘 해결되지 않을때도 많은 것 같다.

하지만 기본적인 계산 방식은 유사하여 몇 번만 잘 공부하여 이해한다면 충분히 수월하게 해결할 수 있는 것 같다.