비서 뽑기 문제임.


지원자의 점수:

s_i (i = 1, 2, ..., n) 이 순서대로 주어지고,

s_i = max(s_1, ..., s_i) 이면 확률 i/n으로 그 지원자를 채용함.


간단하게, 우리가 2번째 지원자를 채용했다 치자.

2번째 지원자를 채용할 확률 = 1번째 지원자를 채용하지 않을 확률 * s_1 < s_2일 확률 * 2번째 지원자를 채용할 확률

= (n-1)/n * 1/2 * 2/n = (n-1)/n^2


근데 여기서 2번째 지원자가 최적의 지원자 (s_2 = max(s_1, ..., s_n)) 이었을 확률을 구해야하는데

잘 이해가 안됨


s_1 < s_2 일 때 s_2가 최적일 확률이 2/n이라서

2/n * (n-1)/n^2

이라는데 왜 2/n 인거임? 머갈통이 빡통인점 양해바란다...