백준 13258, 복권 + 은행

개요

문제 링크
골드 5, 수학
가진돈 만큼의 확률로 J원을 줄 때 C기간 뒤 금액의 기댓값

---

접근

1. 고등학생 때 확통을 열심히 배워야 하는 이유. 기댓값이란 어떤 확률적 시행에 대해 모든 경우의 수를 따져봤을 때 내가 얻을 수 있는 값이다. 쉽게 생각해 A (1% 확률로 100억) vs B (50% 확률로 1억) 중 더 이득인 것을 고를 때 기댓값을 사용한다. 1%의 확률로 100억이 더 손해일 것 같지만 A의 기댓값은 1억, B의 기댓값은 5000만원이라 A가 이득이다.
2. 비슷하게 이 문제를 바라보자. 다음의 과정을 거치기만 하면 문제를 풀 수 있는데,
   1. 1회 시행 후 누군가는 J원을 얻는다. 어떤 $a_i$원을 가진 i번째 사람이 얻을 값은 $p_i$ × J = ($a_i$ / $a_i$의 총합) × J원이다. 값은 J, 확률은 자신의 분율이기 때문이다.
   2. 모두가 공평한 기회를 가지므로 1회 시행 후 $a_i$원을 가진 i번째 사람은 $a_i$ + ($p_i$ × J) 만큼의 기댓값을 가진다.
   3. 그럼 모든 i에 대해 $p_i$는 시행횟수와 관계없이 일정한 값을 갖는다. 왜냐? $a_i$의 총합은 초기 총합값이랑 같고, $p_i$ × J의 총합은 J 이기 때문.
3. 따라서 $a_0$의 C회 시행 후 기댓값은 ($p_i$ × J)를 C번 더한 값이 된다.

---

Pseudo code

pi0 = ai0 / sum(a0)
deltaA0 = pi0 * J

ai1 = ai0 + deltaA0 = ai0 + pi0 * J = ai0 + ai0 / sum(a0) * J
ai2 = ai1 + deltaA1 = ai1 + pi1 * J = ai1 + ai1 / sum(a1) * J
 = (ai0 + ai0 / sum(a0) * J) + ai1 / sum(a1) * J

ai1 / sum(a1) = (ai0 * (1 + 1 / sum(a0) * J)) / (sum(a0) * (1 + 1 / sum(a0) * J))
 = ai0 / sum(a0)

aic = ai0 + (ai0 / sum(a0) * J) * c

---

Source code

// 2020KB, 0ms
#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    double n, j, c, a, s, t;
    cin >> n >> a;
    s = a;
    for (int i = 1; i < n; i++) cin >> t, s += t;
    cin >> j >> c;
    cout.precision(10);
    cout << a + (a / s) * j * c;
}

// 1112KB, 0ms
#include <stdio.h>

int main() {
    double n, j, c, a, s, t;
    scanf("%lf\n%lf", &n, &a);
    s = a;
    for (int i = 1; i < n; i++) scanf("%lf", &t), s += t;
    scanf("%lf\n%lf", &j, &c);
    printf("%.9lf", a + (a / s) * j * c);
}

# 31120KB, 40ms
import sys; input = sys.stdin.readline
def inp():return list(map(float, input().split()))
n, s = float(input()), inp()
a, s, j, c = s[0], sum(s), float(input()), float(input())
print(a + ((a / s) * j) * c)