술 취한 승객
면접 대비시간 제한1초메모리 제한1024 MB
첫 번째 승객이 무작위로 다른 좌석에 앉고 이후 좌석을 빼앗긴 승객이 빈 좌석을 무작위로 고를 때, 마지막 승객의 좌석이 차 있을 확률을 구한다.
문제
COVID-19 때문에 질병의 확산을 막기 위해 일상에서 사회적 거리 두기가 시행되고 있다. 이는 우리의 생활 방식을 많이 바꾸었고, 특히 여행 방식이 그렇다. 이제 많은 항공사가 비지정 좌석을 없애고, 두 승객 사이의 거리가 충분히 멀도록 보장하는 좌석 규칙을 도입하고 있다.
2022 ICPC World Finals에 가는 여행에서 당신은 비행기를 탄다. 비행기는 n명의 승객에게 n개의 지정 좌석을 제공한다. 승객들은 먼저 줄을 서야 하고, 그다음 한 명씩 비행기에 탑승한다. 당신은 줄의 맨 뒤에 있으므로 마지막으로 탑승한다. 안타깝게도 첫 번째 승객이 술에 취해 있다. 술 취한 승객은 무작위로 다른 승객의 좌석으로 가서 거기에 앉는다. 다음을 가정해도 좋다.
- 술 취한 승객은 자신의 좌석에 절대 앉지 않는다.
- 술 취한 승객이 다른 좌석을 선택할 확률은 모두 같다.
다행히 다른 승객은 모두 술에 취하지 않았다. 하지만 그들은 이미 점유된 좌석에서 승객을 내보내고 싶어 하지 않는다. 탑승할 때 자신의 좌석이 다른 승객에게 점유되어 있으면, 그 승객은 같은 확률로 비어 있는 좌석을 무작위로 선택한다. 그렇지 않으면 승객은 자신의 좌석에 그냥 앉는다.
당신의 좌석이 다른 승객에게 점유될 확률을 계산하는 프로그램을 작성하시오.
입력
입력은 양의 정수 n 하나만 주어진다.
출력
당신의 좌석이 다른 승객에게 점유될 확률을 출력한다. 출력과 정답의 차이가 10-6 미만이면 정답으로 인정된다.
제한
- 1 < n ≤ 300
힌트
이 문제의 지문은 허구이다.