백준 23337 (Drunk Passenger)

백준 23337 Drunk Passenger

문제 링크

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

문제 접근

Drunk Passenger Problem

재미있는 문제를 가지고 왔습니다. 외국에서 유행을 조금씩 타고 있는 Drunk Passenger Problem을 들고 왔습니다. N개의 좌석이 있는 비행기에, N명의 손님이 들어오고 있습니다. n번째 손님은 n번 자리에 앉는다고 가정을 해보겠습니다. 여기까지는 큰 어려움이 없습니다. 하지만 유감스럽게도, 첫 번째 손님은 술에 취해서 들어왔습니다. 이 손님은 절대 자신의 자리에 앉지 않는다고 합니다. 1번 손님이 1번을 제외한 랜덤한 자리에 앉는다는 의미인 것입니다.

만약 취객이 k번째 자리에 앉았다고 가정해보겠습니다. k번째 손님은 앉을 자리가 없어졌습니다. 따라서 이 손님도, 남아있는 자리 중 아무 곳이나 균일한 확률로 앉는다고 하겠습니다.

이러한 상황에서 나는 제일 마지막인 손님이라고 가정할 때, 내가 제 자리에 앉지 못할 확률을 구하는 문제입니다.

문제에 들어가기에 앞서, i번째 사람이 자기 자리를 뺏겼을 때, 어떤 특정한 자리를 고를 확률은 같습니다.

소스 코드

마무리하며