난이도

Gold 5

인증

문제

겨울 나라의 왕은 꽃을 좋아하는 왕비를 위해 가장 아름다운 꽃들을 모아 화관을 만들기로 했다. 왕비가 좋아하는 꽃들은 특별해서 마법의 씨앗을 심은 뒤 별빛을 받아야 피어난다. 마법의 씨앗에서 피어날 수 있는 꽃들의 종류는 $N$가지이며, 각 종류의 꽃들이 피어날 확률은 동일하다. 씨앗에서 꽃이 피어날 확률은 다른 씨앗에 영향을 받지 않는다. 화관을 만들기 위해서는 모든 종류의 꽃들이 최소 한 송이씩 필요하다. 화관이 만들어질 때까지 씨앗에서 꽃을 한 송이씩 피운다면, 필요한 씨앗 개수의 기댓값은 얼마일까?

입력

첫 줄에 꽃들의 종류의 수를 의미하는 정수 $N$ ($1 \leq N \leq 1000$) 이 주어진다.

출력

화관을 만들기 위해서 필요한 씨앗 개수의 기댓값을 출력한다. 정답과의 절대 오차/상대 오차 중 하나가 $10^{-4}$ 이하라면 정답으로 인정된다. 구체적으로, 제출한 답이 $a$이고 정답이 $b$일 때 $\frac{|a - b|}{\max(1, |b|)} \leq 10^{-4}$이면 정답으로 인정된다.

예제 입력

1

예제 출력

1.0000000000000000000

해설 및 후기

쿠폰과 매우 유사한 문제이다. 그러나 이는 기약분수 꼴로 처리하는 것이 아닐 뿐더러, N의 값이 매우 커질 수 있다. 때문에 gcd를 이용하지 않고, 더한 분자값을 분모값으로 단순히 나누어 이를 해결할 수 있었다.

제출 코드

from math import gcd

def printAns(n):
    d = 1
    for i in range(2,n+1):
        d *= i
    t = 0
    for i in range(1,n+1):
        t += d//i
    t *= n
    c = gcd(t,d)
    d = d//c
    t = t//c
    print(t/d)

n = int(input())
printAns(n)