BOJ 26217 - 별꽃의 세레나데 (Easy) (Python3)

그간 격조했다. 아직 공대생 신분이기 때문에 기말고사는 피할 수 없는 재앙과도 같다. 다음 학기 장학금을 타 쓰기 위해서라도 시험공부를 게을리 할 수는 없다...!

이 문제는 어제 개최된 개인 대회 겨울 숲의 초대 C번 문제이다. 수학을 좀 아는 사람과 수학을 좀 모르는 사람 사이 체감 난이도 차가 극심한 문제.

개인적으로 연구하던 컴플리트 가챠와 구조가 완전히 동일해서 아주 쉽게 풀었다.

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

겨울 나라의 왕은 꽃을 좋아하는 왕비를 위해 가장 아름다운 꽃들을 모아 화관을 만들기로 했다. 왕비가 좋아하는 꽃들은 특별해서 마법의 씨앗을 심은 뒤 별빛을 받아야 피어난다.

마법의 씨앗에서 피어날 수 있는 꽃들의 종류는 \(N\)가지이며, 각 종류의 꽃들이 피어날 확률은 동일하다. 씨앗에서 꽃이 피어날 확률은 다른 씨앗에 영향을 받지 않는다.

화관을 만들기 위해서는 모든 종류의 꽃들이 최소 한 송이씩 필요하다. 화관이 만들어질 때까지 씨앗에서 꽃을 한 송이씩 피운다면, 필요한 씨앗 개수의 기댓값은 얼마일까?

 

입력

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

 

예제 입력)

# 예제 입력 1
1

# 예제 입력 2
2

# 예제 입력 3
96

# 예제 입력 4
1000

 

출력

화관을 만들기 위해서 필요한 씨앗 개수의 기댓값을 출력한다. 정답과의 절대 오차/상대 오차 중 하나가 \(10^{-4}\) 이하라면 정답으로 인정된다.

구체적으로, 제출한 답이 a이고 정답이 b일 때 \(\frac{|a - b|}{\max(1, |b|)} \leq 10^{-4}\)이면 정답으로 인정된다.

 

예제 출력)

# 예제 출력 1
1.0000000000000000000

# 예제 출력 2
3.0000000000000000000

# 예제 출력 3
494.0892621653223970024

# 예제 출력 4
7485.4708605503449141416

꽃이 2종류인 경우 씨앗 1개를 심으면 두 종류 꽃 중 하나를 피울 수 있다. 이후에 아직 얻지 못한 꽃을 피울 확률은 1/2이므로, 이 꽃을 피우기 위해서는 씨앗이 평균적으로 2개 더 필요하다. 따라서 답은 3이다.

---

내 코드

from math import log, e
gamma = 0.577215664901532
n = int(input())
if n in (1,2):
    print([0,1,3][n]); quit()
ans = log(n,e) + gamma + 1/(2*n)-1/(12*n**2)
ans += 1/(120*n**4) - 1/(252*n**6)
print(ans*n)

 

첫 솔브를 가져가겠다고 머리를 굴린 터라 코드가 조금 지저분하긴 하다. 굳이 e를 안 가지고 와도 자연로그는 log(n)으로 이미 구할 수가 있음을 간과했다...

 

i종의 씨앗이 꽃을 이미 피웠을 때, 씨앗이 이전과 다른 종류의 꽃을 피울 때까지 필요한 씨앗의 기대값을 \(\mathbb{E}(i+1)\)라고 두자.

우선 하나의 씨앗을 꽃피웠을 때 마침 필요한 꽃일 확률은, n종류의 꽃 중 이미 획득한 i종류의 꽃을 제외한 n-i종류의 꽃 중 아무거나 얻어야 하므로 시행과 불문하게 \(\frac{n-i}{n}\)으로 동일하다.

그럼 평균적으로 \(\frac{n}{n-i}\)개의 씨앗을 피우면 아직까지 없던 꽃 중 하나를 획득할 수 있겠지.

이걸 i가 0일 때부터 n-1일 때까지 더해 주면 된다. N의 제한범위가 작으니 그대로 반복문을 돌려도 되지만...

여기는 수학적 공대생의 블로그가 아니던가. 조금은 수학적인 접근법을 사용해 보자!

 

그러면 얻어지는 수는 다음과 같은 수 \(\sum_{i=0}^{n-1}\frac{n}{n-i}=\sum_{i=1}^n \frac{n}{i}\)이다.

이제 조화수 \(H_n=\sum_{i=1}^{n}\frac{1}{i}\)를 도입해 보자. 출력하여야 하는 답은 \(nH_n\)라는 아주 간단한 식으로 표기가 가능하다.

더욱 좋은 점은, \(H_n\)에 대한 매우 정밀한 점근근사식이 나와 있다는 것이다. 증명은 간단히 끝낼 수준이 아니기에 별도의 포스트에서 다루도록 하고, 여기에선 그 결과만 뽑아 먹도록 하자.

\[ H_n\sim \log n + \gamma + \frac1{2n} - \sum_{k=1}^\infty \frac{B_{2k}}{2kn^{2k}}\]

여기서 \(\gamma=0.57721\,56649\,05132\,86060\cdots\)는 오일러-마스케로니 상수라는 이름난 상수이고, \(B_n\)은 \(\frac{d^n}{dx^n}\frac{x}{e^x-1}\mid_{x=0}\)으로 정의되는 베르누이 수이다.

여기서는 오차가 매우 널널하기 때문에, n>2인 경우는 \(n^{-6}\)항까지만 계산해도 벗어나지 않는다.

베르누이 수의 첫 몇 개의 항은 다음과 같으니, 그대로 대입해서 풀어버리면 끝!

\[B_0=1, B_1=-\frac{1}{2}, B_2=\frac{1}{6}, B_3=0, B_4=-\frac{1}{30}, B_5=0, B_6=\frac{1}{42}\]

 

이로서 26217번의 풀이를 마친다.

그럼, 오늘도 당신의 코딩 실력이 상승하기를.