레이팅 미적용설명
카드 뽑기 기계에는 \(N\)가지 종류의 쿠폰이 동일한 확률로 들어 있다. 매 뽑기마다 각 종류가 \(\frac{1}{N}\) 확률로 나온다. 모든 종류의 쿠폰을 최소 \(1\)장씩 모으기 위해 뽑아야 하는 횟수의 기댓값을 구하여라.
답은 기약분수 \(P/Q\) 형태로 출력한다.
제약
- \(1 \le N \le 1\,000\)
입력 형식
한 줄에 쿠폰 종류 수 \(N\)이 주어진다.
출력 형식
기댓값을 기약분수 \(P/Q\) 형태로 한 줄에 출력한다. (\(\gcd(P, Q) = 1\), \(Q \ge 1\))
예제 1
입력
1
출력
1/1
설명
쿠폰 종류가 \(1\)개뿐이므로 첫 번째 뽑는 즉시 모든 종류가 완성된다. 기댓값은 \(1\)이다.
예제 2
입력
2
출력
3/1
설명
첫 번째는 무조건 새 쿠폰 (\(1\)번). 두 번째부터는 확률 \(\frac{1}{2}\)로 새 쿠폰. 기댓값 = \(1 + 2 = 3\)이다.
문제 정보
riseoj 작성
출처 Original
태그